Блог пользователя otero1991

Minimum Diameter Spanning Tree
Автор otero1991, 12 лет назад, По-английски

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
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +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).

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← 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

    → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← 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 года назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
← 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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← 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 лет назад, # |
  Проголосовать: нравится +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

→ Ответить