patternMinor
Minimum diameter spanning tree problem
Viewed 0 times
problemminimumdiameterspanningtree
Problem
Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the spanning tree $T(V, E')$ of $G$ such as maximal distance between vertices in $T$ is minimal.
I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $\Theta(n^3)$ solution exists here, but no full solution is anywhere.
I believe this community would benefit if solution is described here.
I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $\Theta(n^3)$ solution exists here, but no full solution is anywhere.
I believe this community would benefit if solution is described here.
Solution
The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows.
The absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a shortest path tree connecting $v$ to all vertices in $V$. It holds that $T(a)$ is a minimum diameter spanning tree of $G$, where $a$ is an absolute 1-center of $G$. Here, if the absolute 1-center is an edge, we subdivide it to obtain the vertex $a$ from which $T(a)$ is then computed from.
An absolute 1-center $a$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $T(a)$ is computed by any standard shortest path algorithm.
The absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a shortest path tree connecting $v$ to all vertices in $V$. It holds that $T(a)$ is a minimum diameter spanning tree of $G$, where $a$ is an absolute 1-center of $G$. Here, if the absolute 1-center is an edge, we subdivide it to obtain the vertex $a$ from which $T(a)$ is then computed from.
An absolute 1-center $a$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $T(a)$ is computed by any standard shortest path algorithm.
Context
StackExchange Computer Science Q#105822, answer score: 7
Revisions (0)
No revisions yet.