Question About Minimum Spanning Tree

Discussion in 'C++' started by BigBaz, Nov 20, 2008.

  1. BigBaz

    BigBaz Guest

    Given a graph G and a minimum spanning tree T, suppose that we
    decrease the weight of one of the edges that is not in T. Give an
    algorithm that finds the minimum spanning tree in the modified graph.

    Thanks in advance.
     
    BigBaz, Nov 20, 2008
    #1
    1. Advertising

  2. BigBaz

    Giff Guest

    BigBaz wrote:

    > Thanks in advance.


    What is the question? And what is the c++-related question?
     
    Giff, Nov 20, 2008
    #2
    1. Advertising

  3. BigBaz wrote:
    > Given a graph G and a minimum spanning tree T, suppose that we
    > decrease the weight of one of the edges that is not in T. Give an
    > algorithm that finds the minimum spanning tree in the modified graph.


    You are supposed to do your homework yourself, not ask others to do it
    for you.
     
    Juha Nieminen, Nov 20, 2008
    #3
  4. BigBaz

    BigBaz Guest

    On Nov 20, 9:53 am, red floyd <> wrote:
    Yes, I will try to do it myself. But this algorithm is different from
    the normal algorithm of finding mst, otherwise the question will just
    ask me how to find a mst. So clearly there's some difference. Any help
    would be appreciated.

    Jeff_Schwab, is your algorithm efficient? Thanks!



    > BigBaz wrote:
    > > Given a graph G and a minimum spanning tree T, suppose that we
    > > decrease the weight of one of the edges that is not in T. Give an
    > > algorithm that finds the minimum spanning tree in the modified graph.

    >
    > > Thanks in advance.

    >
    > A complete answer can be found here:
    >
    > http://www.parashift.com/c -faq-lite/how-to-post.html#faq-5.2
    >
    > Hope that helps.
     
    BigBaz, Nov 20, 2008
    #4
  5. On 2008-11-20 11:04, BigBaz wrote:
    > Given a graph G and a minimum spanning tree T, suppose that we
    > decrease the weight of one of the edges that is not in T. Give an
    > algorithm that finds the minimum spanning tree in the modified graph.


    T' = T

    > Thanks in advance.


    Your welcome.

    --
    Erik Wikström
     
    Erik Wikström, Nov 20, 2008
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?U2hlcg==?=

    Compressing and spanning files on upload

    =?Utf-8?B?U2hlcg==?=, Dec 23, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    503
    =?Utf-8?B?U2hlcg==?=
    Dec 28, 2005
  2. _mario.lat
    Replies:
    2
    Views:
    6,672
    Dietmar Kuehl
    Jul 5, 2004
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,244
  4. Josh Close
    Replies:
    3
    Views:
    443
    Josh Close
    Aug 16, 2004
  5. tonokio
    Replies:
    2
    Views:
    492
    Alan Johnson
    May 3, 2006
Loading...

Share This Page