Tagged: CS & IT, gate, Graduate Engineering, Sectional Tests

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

- AuthorPosts
- 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 :-

- MaxST has a polynomial time algorithm; LongP has a polynomial time algorithm except when the graph contains negative weight cycle.
- MaxST has a polynomial time algorithm till date; LongP has an Exponential time algorithm except when the graph contains negative weight cycle.
- MaxST has no polynomial time algorithm till date; LongP has a Exponential time algorithm except when the graph contains negative weight cycle.
- MaxST has no polynomial time algorithm till date; LongP has no polynomial time problem except for Directed acyclic graph.

Post your Training /Course EnquiryAre You looking institutes / coaching center for- IIT-JEE, NEET, CAT
- Bank PO, SSC, Railways
- Study Abroad

- AuthorPosts