Bipartite-coloring approximation conjecture for planar MAX-EMST-ratio
Bipartite-coloring approximation conjecture for planar MAX-EMST-ratio
Let be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of and partitioning so that every edge of the chosen tree has endpoints of different colors. Bipartite-coloring approximation conjecture. For every point set in , the EMST-ratio for any bipartite coloring is a -approximation for the maximum EMST-ratio.
The source presents triangular chains as examples whose approximation proportion approaches , and notes that proving this conjecture would yield an -time -approximation algorithm for the planar problem.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Afrouz Jabal Ameli, Faezeh Motiei and Morteza Saghafian, “On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum”, arXiv:2409.11079 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.