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

  • Author
    Posts
  • #1440034 Reply
     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.
    Post your Training /Course Enquiry
    Are You looking institutes / coaching center for
    • IIT-JEE, NEET, CAT
    • Bank PO, SSC, Railways
    • Study Abroad
    Select your Training / Study category
Reply To: Maximum Spanning tree problem (MaxST) defined for a weighted Undirected Graph aims to compute the sp….
Your information:




Verify Yourself




Log in with your credentials

or    

Forgot your details?

Create Account