Polynomial-time fixed-topology minimum-bead tree conjecture
Polynomial-time fixed-topology minimum-bead tree conjecture
Let be a set of terminals embedded in the Euclidean plane, and let be any tree topology on whose Steiner points have degree at least three. Fixed-topology bead-minimization conjecture. Finding a tree on with the same topology as and minimizing can be done in polynomial time. This conjecture is motivated by the prospect of a polynomial-time algorithm based on displacing Steiner points of a Steiner minimum tree; the supplied text gives no resolution.
Sources & referencesView supporting material
Primary source
M. Brazil, C. J. Ras and D. A. Thomas, “Approximating Minimum Steiner Point Trees in Minkowski Planes”, arXiv:1307.2987 (2013).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.