On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

被引：0

作者：

Criel Merino

Gelasio Salazar

Jorge Urrutia

机构：

[1] Universidad Nacional Autónoma de México,Instituto de Matemáticas

[2] Universidad Autónoma de San Luis Potosí,Instituto de Investigación en Comunicación Óptica

来源：

Graphs and Combinatorics | 2005年 / 21卷

关键词：

Geometric graphs; Perfect matchings; Minimum weight perfect matchings;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M1 and M2 be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M1 and M2 intersect at most |M1|+|M2|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp.

引用

页码：333 / 341

页数：8

共 19 条

[1]

Akiyama J.(1990)Simple alternating path problems Discrete Math. 84 101-103

[2]

Urrutia J.(2002)Partitioning colored point sets into monochromatic parts Int. J. Comput. Geom. Appl. 12 401-412

[3]

Dumitrescu A.(2001)Matching colored points in the plane, some new results Comput. Geom. Theory Appl. 19 69-85

[4]

Pach J.(2000)On a matching problem on the plane Discrete Math. 211 183-195

[5]

Dumitrescu A.(2005)On spanning trees and cycles of multicolored point sets with few intersections Inf. Process. Lett. 93 301-306

[6]

Kaye R.(1995)Ramsey-type results for geometric graphs, I Discrete Comput. Geom. 18 247-255

[7]

Dumitrescu A.(1998)Ramsey-type results for geometric graphs, II Discrete Comput. Geom. 20 375-388

[8]

Steiger W.(1996)Crossing number of two-connected geometric graphs Inf. Process. Lett 59 331-333

[9]

Kano M.(undefined)undefined undefined undefined undefined-undefined

[10]

Merino C.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →