otero1991's blog

Minimum Diameter Spanning Tree
By otero1991, 12 years ago, In English

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.

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

»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

there are 1000 vertexes , but my way is n^3 ,so let's wait for some cows to reply

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

http://www.spoj.com/problems/PT07C/ i think this problem is a similar problem , but there are only 200 nodes

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

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).

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

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -16 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can split each edge by a fake vertex.

      UPD. Oh, this is for unweighted graph.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm looking for an algorithm for weighted graphs!!

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      O(nm) = O(n3), because m = O(n2) it depends on how many edges in the graph.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -14 Vote: I do not like it

    I fixed my code, had a stupid mistake. If anyone is struggling with the problem I wrote a blog explaining the solution:)).

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "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.. :/

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

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    "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]);

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

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

→ Reply