Rubinstein–Weng–Wormald linear-error conjecture for minimum-topology approximate Steiner trees
Rubinstein–Weng–Wormald linear-error conjecture for minimum-topology approximate Steiner trees
Let an -approximate Steiner tree be a tree whose angles at Steiner points lie in . For , let be the subset of full -approximate Steiner trees on terminals in whose terminals have a minimum Steiner tree with the same topology. If
where is the shortest tree with the topology of , then Rubinstein–Weng–Wormald's conjecture. For any there exist and such that for all and ,
The conjecture gives the same uniform linear error bound when the prescribed topology is realized by a minimum Steiner tree; the supplied text states that this case remains open.
Sources & referencesView supporting material
Primary source
Charl Ras, Konrad J. Swanepoel and Doreen Thomas, “Approximate Euclidean Steiner Trees”, arXiv:1605.01172 (2016).
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.