in Written Exam
361 views
0 votes
0 votes
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 a given destination. Which of the following statements is correct:

A. MaxST has a polynomial time algorithm, and LongP does not have any polynomial time algorithm till date except for directed acyclic graphs.

B. MaxST as well as LongP problem don’t have any polynomial time algorithm till date. However, for directed acyclic graph, there is a polynomial time algorithm for LongP.

C. MaxST has a polynomial time algorithm; LongP has a polynomial time algorithm except when the graph has a negative cycle.

D. MaxST has a polynomial time algorithm provided there are no negative edge weights, and LongP does not have any polynomial time algorithm till date except for directed acyclic graphs.
in Written Exam
361 views

1 Answer

1 vote
1 vote
Best answer

Option A is correct

MaxST can be solved in polynomial time.

Just negate the weights of the edges of the graph and apply Kruskal for finding minimum spanning tree.

LongP is a Np complete problem so it takes exponential time dont have any polynomial time except for DAG (directed acyclic graph)

The algo for finding the LongP in DAG is given below.

Let us assume v0,v1,.....vn be n vertices of the dag

Suppose v0 be the source from where we have to calculate the LongP for the dag

Here we take a queue Q and an array C[n]

Initialise C[i] = - infinity for i>0 and C[0] =0

STEP 1 Enqueue v

STEP 2 Enqueue all vertices present in the adjacency list of head(Q) which are not queued already

If any vertex vj is adjacent to head(Q) then C[j] = max ( C[j] , C[head(Q)] + weight of the edge (head(Q),vj ) )

STEP 3 Dequeue and then go to STEP 2 repeat STEP 2 and STEP 3 until there is no vertex left be queued.

STEP 4 Return max of the array C.

The above algo will take O(V + E) time.

selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true