Bi-ChromaticMinimumSpanningTrees创新.PDFVIP

EWCG 2005, Eindhoven, March 9–11, 2005 Bi-Chromatic Minimum Spanning Trees Magdalene Grantson Henk Meijer David Rappaport∗ Abstract sup Pgp ≥ 2 sup Lgp = ∞ sup Lgp − Ls ≥ 2 H Pop G Lop G Lop − Ls Let G be a set of disjoint bi-chromatic straight line sup Pgp ≥ 2 sup Lgp = ∞ sup Lgp − Ls ≥ 2 segments and H be a set of red and blue points in H Puo G Luo G Luo − Ls the plane, no three points are collinear. We give tight sup Pop ≥ 2 sup Lop = ∞ sup Lop − Ls ≥ 3 H Puo G Luo G Luo − Ls 2 upper bounds on the maximum degree of a node in the color conforming minimum weight spanning tree Table 1: An overview of some of our results. (MST) formed by G and H . We also consider bounds on the total length of the edges of 1) the planar MST and the unrestricted MST, 2) the greedy planar span- creasing length order, and discards edges creating a ning tree and the unrestricted MST, 3) the greedy cycle in the graph built so far [8].) We show by illus- planar spanning tree and the planar MST. tration that Kruskal’s algorithm may also introduce intersections, when