4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ You may be interested by researchgate.net/publication/…. I did not read the full article but the authors claim that a $\Theta(n^3)$ solution stands when working in Euclidian plane. The general weighted graph problem would be NP-complete. $\endgroup$
    – Optidad
    Commented Mar 20, 2019 at 9:38
  • $\begingroup$ @Vince Are you allowing for non-positive edge weights as well when you say it is NPC? $\endgroup$
    – Juho
    Commented Mar 20, 2019 at 9:48

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I believe it'd be great to have the full algorithm description, at least brief, in one place. Here, for example :) $\endgroup$
    – hse_one_love
    Commented Mar 20, 2019 at 11:02
  • 2
    $\begingroup$ @hse_one_love I sympathize, full details are often omitted in research papers and some work is needed for a real implementation (and doing this can sometimes even uncover errors or severe omissions). Perhaps this answer on StackOverflow is helpful. $\endgroup$
    – Juho
    Commented Mar 20, 2019 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.