Updated a Minimum Spanning Tree in O(V) time?

This is a discussion on Updated a Minimum Spanning Tree in O(V) time? within the C Programming forums, part of the General Programming Boards category; I have a weighted, undirected graph. I have a Minimum Spanning Tree for that graph. One edge (u,v), with weight ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    11

    Updated a Minimum Spanning Tree in O(V) time?

    I have a weighted, undirected graph. I have a Minimum Spanning Tree for that graph. One edge (u,v), with weight w, is added to the graph.

    How can I update the minimum spanning tree in O(V) time?

    I think of it as adding an edge to the MST, and then deciding, in O(V) time, which edge has to then be removed.

    Anyone have any ideas?

  2. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by scp89 View Post
    Anyone have any ideas?
    Yes.

    Assuming that your graph is connected (i.e. there is a path from any node to any other node), adding a new edge to the MST makes the resulting graph MST' cyclic. Hence it suffices to do a DFS on the original MST starting from u and searching for v. This will yield exactly one (u,v)-path. If its highest edge weight is larger than w((u,v))=w, remove the corresponding edge and add (u,v) to the MST, otherwise don't do anything.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    11
    Thanks!

  4. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    If this is some kind of homework, you additionally might want to argue why DFS doesn't violate the O(|V|) constraint, because all the textbooks are claiming that DFS takes time O(|V| + |E|).

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 02:28 PM
  2. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 03:48 PM
  3. Is this really true or it's just science fiction?
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 145
    Last Post: 04-09-2002, 07:17 PM
  4. Minimum spanning trees
    By hansy32 in forum C Programming
    Replies: 1
    Last Post: 03-14-2002, 09:07 AM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 10:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21