yosupo06/library-checker-problems

[Problem proposal] Minimum Diameter Spanning Tree

Closed this issue · 2 comments

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

Note / Disucussion

  • Weighted graph or unweighted graph? For unweighted graph there exists $O(\frac{n^3}w)$.
  • Dense graph or sparse graph?
  • 辺重みについて:重みありの方が細かい処理の正確な実装を 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.