Monotonicity of worst-case bottleneck values for the (δ,k)(\delta,k)-PKRY algorithm

From papers

For each mm, let SmS_m be a star with mm children rooted at its centre vertex, chosen to maximise the length of the longest edge in the tree produced by the (δ,k)(\delta,k)-PKRY algorithm, with every child at unit distance from the centre and no pair of children at distance less than 11. Define Sm+1S_{m+1} similarly with m+1m+1 children. Let bb and bb' be the bottleneck values of the outputs of (δ,k)(\delta,k)-PKRY on SmS_m and Sm+1S_{m+1}, respectively. PKRY monotonicity conjecture. Then bbb \geq b'. 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

No solutions have been posted yet.