1. Suppose that an instance of bipartite matching has 10 vertices in the left co

Question

1. Suppose that an instance of bipartite matching has 10 vertices in the left column, 15 vertices in the right column, and 30 edges. The number of edges in the corresponding instance of network flow is:

      A. 25               B. 30               C. 55               D. 150

2. The capacity of the following cut is ______. (S vertices are bold.

A. 1                 B. 10               C. 15               D. 23

3. The Edmonds-Karp variant is important because:

A.   It solves the bipartite matching problem.

B.   It solves the network flow problem in polynomial time.

C.   It solves the network flow problem using critical edges.

D.   It solves the network flow problem without using augmenting paths.

Explanation / Answer

3. The Edmonds-Karp variant is important because:

  B.   It solves the network flow problem in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.