[Problem proposal] Minimum Diameter Spanning Tree
Closed this issue · 2 comments
robinyqc commented
Problem name: Minimum Diameter Spanning Tree
Problem ID: minimum_diameter_spanning_tree
Problem
Given a simple connected undirected graph with
Constraint
Depends on the way to calculate all-pairs shortest path.
Solution / Reference
Note / Disucussion
- Weighted graph or unweighted graph? For unweighted graph there exists
$O(\frac{n^3}w)$ . - Dense graph or sparse graph?
maspypy commented
Japanese Reference
https://www.slideshare.net/slideshow/ss-17402143/17402143
maspypy commented
- 辺重みについて:重みありの方が細かい処理の正確な実装を 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.