[Problem proposal] Minimum Diameter Spanning Tree

[robinyqc]

Problem name: Minimum Diameter Spanning Tree Problem ID: minimum_diameter_spanning_tree

Problem

Given a simple connected undirected graph with $n$ vertices and $m$ edges, find the spanning tree with minimum diameter.

Constraint

Depends on the way to calculate all-pairs shortest path.

Solution / Reference

• OI-Wiki (in Chinese)
• https://codeforces.com/blog/entry/7372
• CF 266D
• SPOJ MDST

Note / Disucussion

• Weighted graph or unweighted graph? For unweighted graph there exists $O(\frac{n^3}w)$.
• Dense graph or sparse graph?

[maspypy]

Japanese Reference https://www.slideshare.net/slideshow/ss-17402143/17402143

[maspypy]

• 辺重みについて：重みありの方が細かい処理の正確な実装を verify できるため，重みありにしたいと思います．
• 密であるか疎であるか：密グラフに限定したいという特別な理由が特にないので、他の多くの問題と同じように疎グラフでよいと思います．細かい制約は実装してみてからの調整だと思いますが，例えば $n,m\leq 2000$ 程度とすることが考えられると思います．
• その他の制約や入出力形式については， https://judge.yosupo.jp/problem/minimum_spanning_tree を利用できそうです．

---

• Regarding edge weights: I would prefer weighted edges since they allow for more precise verification of the detailed implementation.
• Dense or sparse: Since there is no particular reason to limit it to dense graphs, I think a sparse graph would be fine, just like many other problems. Detailed constraints can be adjusted after implementation, but for example, setting $n,m \leq 2000$ might be considered.
• As for other constraints and input/output formats, we can refer to https://judge.yosupo.jp/problem/minimum_spanning_tree.