0xA28's blog

MDST : Minimum Diameter Spanning Tree
By 0xA28, history, 9 years ago, In English

Given positively weighted undirected graph G find a Spanning tree T which has the smallest possible diameter. (Tree diameter :is the maximum path over all the Shortest paths in the tree) Example Problems :

http://www.spoj.com/problems/PT07C/

http://www.spoj.com/problems/MDST/

I couldn't find any proper explanation for a solution to this problem, However i observed some cool stuff; if the graph we are dealing with was unweighted graph then we can solve this problem by bruteforcing every possible node and edge(cutting it with dummy node) and assume it as the center of our MDST then get SPT(shortest path tree) from this node and calculate it's diameter, The true MDST will be the one SPT which has the smallest diameter.

But in the Weighted Graph, things will be a little bit different when we try to cut an edge to place our dummy node, Where we should place it to get our MDST ? and is there more than a MDST or just a unique one ?

Note : i found this code by chance, but i couldn't manage to understand it

https://github.com/Malatawy15/Algorithms-Library/blob/master/Libraries/Minimum%20Diameter%20Spanning%20Tree.cpp

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 0xA28 (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I couldn't find a solution. I hope someone else would help.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Notes:-

*The shortest path tree (SPT) from a single node could be easily constructed using any SSSP (single source shortest path) algorithm like dijkstra.

*The Center of MDST is the general node ( original node or dummy node ) which gets the SPT with the shortest possible tree diameter, in another words; given the diameter of the MDST with length L, the Center will be the General node which placed on the median position on that diameter (L / 2).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Refer to problem C in this resource. It provides a O(n*m) $$$O(n^{3})$$$ algorithm for MDST on weighted graphs.

Similar problem on Codeforces: 266D — BerDonalds. Here is my implementation in C++: 72562015

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It's funny how in the editorial they say that the complexity of the algorithm is obviously $$$O(n \cdot m)$$$, whereas obviously the first line of the algorithm is applying the Floyd-Warshall algorithm :).

    → Reply