### otero1991's blog

By otero1991, 11 years ago,

I'm trying to find an algorithm for computing a minimum diameter spanning tree of a graph or just the length of the diameter of a minimum diameter spanning tree. There is a problem on SPOJ related with this:(http://www.spoj.com/problems/MDST) . I wonder if somebody could help me to find some information about this.

• +3

 » 11 years ago, # |   -8 there are 1000 vertexes , but my way is n^3 ,so let's wait for some cows to reply
•  » » 11 years ago, # ^ |   0 Could you tell me your n^3 solution!
 » 11 years ago, # |   +4 http://www.spoj.com/problems/PT07C/ i think this problem is a similar problem , but there are only 200 nodes
 » 11 years ago, # |   +2 It's solvable in O(nm) [submit_id = 9109775, running_time = 0.77].For each vertex v do bfs(v), so you have all distances d[i, j].After it brute force center of MDST (it's a vertex or an edge).
•  » » 11 years ago, # ^ |   +1 How can we know the constraint on t to be sure that our solution can pass tests? I didn't find it in the problem statement. Generally, I have this problem with most of the SPOJ's problems.
•  » » 11 years ago, # ^ | ← Rev. 2 →   -16 But when the center is on an edge it's not so easy!! is it?? Could you explain more about this?? Thanks in advance!UPD: I mean that is not so easy when the center is on an edge in weighted graphs
•  » » » 11 years ago, # ^ | ← Rev. 2 →   0 You can split each edge by a fake vertex.UPD. Oh, this is for unweighted graph.
•  » » » » 11 years ago, # ^ |   0 I'm looking for an algorithm for weighted graphs!!
•  » » » » » 10 years ago, # ^ | ← Rev. 4 →   0 I think this algorithm can be converted for weighted graph :For each vertex as a root find it's shortest path tree and calculate it's diameter. Could someone confirm this?
•  » » 11 years ago, # ^ |   0 Wouldn't it take O(n^3) time to find distances between all pairs of vertices? I don't quite understand this part of the implementation.
•  » » » 10 years ago, # ^ |   0 O(nm) = O(n3), because m = O(n2) it depends on how many edges in the graph.
•  » » » » 9 years ago, # ^ |   0 Not for sparse graphs.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -14 I fixed my code, had a stupid mistake. If anyone is struggling with the problem I wrote a blog explaining the solution:)).
•  » » 4 years ago, # ^ |   0 "After it brute force center of MDST (it's a vertex or an edge)." Could not understand, why would we need to find the center of the diameter? Why it is not enough, if we do bfs for every node, and count the minimum diameter for every possible root?Well I tried this approach, and got wa after 4th test case.. :/
 » 10 years ago, # | ← Rev. 3 →   0 Can anybody give a proof why calculating only shortest path tree for all nodes as a root gives us a correct output? Their are many other tree configurations possible,which might give us the shortest diameter.EDIT:In context to THIS Thank you.
 » 9 years ago, # |   0 Are you sure calculating shortest path tree for every vertex logic is correct ? I implimented it for this problem ->http://www.spoj.com/problems/PT07C/ but got WA . http://ideone.com/YDRLYF
•  » » 9 years ago, # ^ | ← Rev. 5 →   0 "After it brute force center of MDST (it's a vertex or an edge)."You should check not only vertices, but also pairs of adjacent vertices. Look at the graph 1-2-3-4. The center of a graph is an edge between vertices 2 and 3. Bruteforce all edges. Do not run bfs for each edge. Calculate distance via dist[(edge (a, b))][i] = min(dist[a][i], dist[b][i]);
 » 5 years ago, # |   +8 In case anyone wants to learn about Min. Diameter Spanning Tree (MDST) on a weighted graph, here's a very good resource: Explanation of problem C in pdf.Here's a problem that requires this idea: 266D - BerDonalds