On the red/blue spanning tree problem

DOI10.1016/J.TCS.2010.10.038MaRDI QIDQ534557zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, Boting Yang, Binhai Zhu, Minghui Jiang

Publication date 18 May 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.10.038

zbMATH Keywords

computational geometryspanning treecrossing number

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the Red/Blue Spanning Tree Problem
• Planar bichromatic minimum spanning trees
• Connecting colored point sets
• Spanning trees in multipartite geometric graphs
• Intersection number of two connected geometric graphs

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Algorithms and Computation
• Crossing Number is NP-Complete
• Crossing number is hard for cubic graphs
• How to draw a planar graph on a grid
• On the convex layers of a planar set
• Planar bichromatic minimum spanning trees

Cited in

(11)

• Short plane supports for spatial hypergraphs
• On the Red/Blue Spanning Tree Problem
• Geometric spanning cycles in bichromatic point sets
• On the number of intersections of three monochromatic trees in the plane
• Planar bichromatic bottleneck spanning trees
• Geometric planar networks on bichromatic collinear points
• Planar Bichromatic Bottleneck Spanning Trees
• Colored spanning graphs for set visualization
• Colored spanning graphs for set visualization
• Short plane supports for spatial hypergraphs
• Faster algorithms for the minimum red-blue-purple spanning graph problem

This page was built for publication: On the red/blue spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534557)