Yes you are right ,sorry..I thought something completely
different..(unfortunately..:( )
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I believe that your problem may be np hard ,because you may construct a
polynomial reduction from maximum length path in a graph (which is
NP-Complete).It is quite interesting that exists such a dichotomy
between minimum vs maximum path in graph(P vs NP).Also i have an idea
that you may construct
Max spanning forest is not NP hardu can write a simple kruskal
algorithm that runs in )(E log* V) for thisas u can see it is
definitely polynomial unlike longest path problem
Siva
--~--~-~--~~~---~--~~
You received this message because you are subscribed
Siva wrote:
Max spanning forest is not NP hardu can write a simple kruskal
algorithm that runs in )(E log* V) for thisas u can see it is
definitely polynomial unlike longest path problem
Siva
Or u can write Prim's algorithm which has the same complexity. But for
some graphs it has
, 2006 10:33 PM
Subject: [algogeeks] Re: Maximum spanning forest
Max spanning forest is not NP hardu can write a simple kruskal
algorithm that runs in )(E log* V) for thisas u can see it is
definitely polynomial unlike longest path problem
Siva
