This topic contains 0 replies, has 0 voices, and was last updated by  EduGorilla 1 year, 11 months ago.

• Author
Posts
EduGorilla
Keymaster
Select Question Language :

Maximum Spanning tree problem (MaxST) defined for a weighted Undirected Graph aims to compute the spanning tree of maximum weight. Longest path Problem (longP) in a weighted directed graph aims to compute path of maximum weight from a given source to given destination. Which of the following is correct?

### Options :-

1. MaxST has a polynomial time algorithm; LongP has a polynomial time algorithm except when the graph contains negative weight cycle.
2. MaxST has a polynomial time algorithm till date; LongP has an Exponential time algorithm except when the graph contains negative weight cycle.
3. MaxST has no polynomial time algorithm till date; LongP has a Exponential time algorithm except when the graph contains negative weight cycle.
4. MaxST has no polynomial time algorithm till date; LongP has no polynomial time problem except for Directed acyclic graph.
Are You looking institutes / coaching center for
• IIT-JEE, NEET, CAT
• Bank PO, SSC, Railways
Select your Training / Study category
Reply To: Maximum Spanning tree problem (MaxST) defined for a weighted Undirected Graph aims to compute the sp….

Verify Yourself