Monotonicity of worst-case bottleneck values for degree-bounded spanning trees
Monotonicity of worst-case bottleneck values for degree-bounded spanning trees
Let be a root vertex with children , where , the angles between children with respect to are at least , and all children have radial distance . Let be the optimal bottleneck path that starts at and visits all children, and suppose that the children are placed to maximise the bottleneck length of . Likewise, let be a root vertex with children , with pairwise angles at least and radial distances equal to . Let be the optimal bottleneck path that starts at and visits all children, and suppose that the children are placed to maximise the bottleneck length of . Monotonicity conjecture. Then . This asserts that adding a child cannot increase the worst-case bottleneck value. The claim is motivated by analytical and experimental point sets, but no proof or resolution is supplied here.
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
Patrick J. Andersen and Charl J. Ras, “Degree Bounded Bottleneck Spanning Trees in Three Dimensions”, arXiv:1812.11177 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.