Polynomial-time fixed-topology minimum-bead tree conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.