Monotonicity of worst-case bottleneck values for the -PKRY algorithm
Monotonicity of worst-case bottleneck values for the -PKRY algorithm
For each , let be a star with children rooted at its centre vertex, chosen to maximise the length of the longest edge in the tree produced by the -PKRY algorithm, with every child at unit distance from the centre and no pair of children at distance less than . Define similarly with children. Let and be the bottleneck values of the outputs of -PKRY on and , respectively. PKRY monotonicity conjecture. Then . This is presented as a monotonicity property for worst-case arrangements, and the source describes it as a stronger version of an earlier conjecture; 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.