We have a weighted directed graph with the following n = 3k vertices: V = {a1, .

Question

We have a weighted directed graph with the following n = 3k vertices:

V = {a1, . . . , ak, b1, . . . , bk, c1, . . . , ck}

and the following 2k 2 edges:

E = {(ai , bj )|i, j {1, . . . , k}} {(bi , cj )|i, j {1, . . . , k}}

Each edge-weight is a positive real number. We want to find a collection of k disjoint paths P1, . . . , Pk where Pi starts at ai and ends at ci (for i {1, . . . , k}). (Paths are disjoint if they do not share any vertices.) Our objective is to minimize the total length of the paths (that is, the function we want to minimize is the length of P1 plus the length of P2 plus the length of P3 . . . plus the length of Pk).

The input is k and all the edge weights, that is, w((a1, b1)), . . . , w((ak, bk)), w((b1, c1)), . . . , w((bk, ck))

Give a fast algorithm for the problem. Clear description of the algorithm is sufficient. Clearly state what algorithm you are using, what is its running time, and what input you are running it on. Your algorithm should run in polynomial time.

Explanation / Answer

Let A={a1,a2,...,ak} , B={b1,b2,...,bk} and C={c1,c2,...,ck}

Algorithm

1. Sort the edges between A and B in increasing order of weights w((a1, b1)), . . . , w((ak, bk)) and stored in linked list E.

2. Select first edge in E i.e. minimum weight edge e=(a1,b1) for path, and delete the edges in E that contain either a1 or b1.

3. Repeat step 2 till the linked list E is not empty.

4. Thus we will have collection of disjoint edges between A and B covering all the vertices in A and B.

5. Repeat step 1 to step 3 for edges between B and C which will give collection of disjoint edges between B and C, covering all the vertices in B and C.

Important points:-
1. Since we are picking disjoint edges between each of bipartite graph A and B, B and C with minimum edge picked first. This will give minimum possible sum of weights over disjoint edges covering all the vertices.
2. Thus input of above algorithm is the set of weights w((a1, b1)), . . . , w((ak, bk)), w((b1, c1)), . . . , w((bk, ck)) and output will be the set of selected edges for paths P1,P2,...,Pk.
3. Since edges between A and B are disjoint, and edges between B and C are disjoint. So all the paths P1,P2,...,Pk will be disjoint.

Time complexity:-

For calculating edges between A and B, we are sorting the weights w((a1, b1)), . . . , w((ak, bk)) which will take O(k2 log k2). Then traversing over the linked list E will take O(k2) times and we are doing this traversal maximum O(k2) times till the list E is not empty. So total traversal takes O(k2*k2)=O(k4). Similar things we are doing for edges between B and C. So total complexity = 2*{O(k2logk2)+O(k4)} = O(k4).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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