Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS535 Homework 3

2022

1. Let D = (V； A; c) be a flow network and x be a b-TS in D under c. Note that c(V))= b (V) = 0. Describe a linear-time algorithm for finding the minimal set U containing a given node v 2 V satisfying that c(U)) = b (U).

2. Let D = (V； A; c) be a flow network with positive integer edge capacities, and f be an integer maximum s-t flow in D from a source s to a sink t. Suppose now an edge a 2 A has capacity reduced by 1. Describe a linear-time algorithm for finding a maximum s-t flow in D after the capacity change.

3. Let D = (V； A; c) be a flow network with distinct source s and sink t. An edge a 2 A is essential if it is saturated by all maximum s-t flows. Given a maximum s-t flow f, describe a linear-time algorithm for finding all essential edges.

4. A set J of jobs are to be scheduled on m identical machines. Each job j 2 J has a processing requirement pj (denoting the number of machine days required to complete the job), a release date rj (representing the beginning of the day when job j becomes available for processing), and a due date dj > rj + pj (representing the beginning of the day by which the job must be completed). We assume that a machine can work on only one job at a time and that each job can be processed by at most one machine at a time. However, we allow preemptions (i.e., we can interrupt a job and process it on different machines on different days). The scheduling problem is to determine a feasible schedule that completes all jobs before their due dates or to show that no such schedule exists. Formulate this problem as a maximum flow problem.

5. A commander is located at one node p in a communication network D and his subordinates are located at nodes denoted by the set S. Let cj be the effort required to eliminate arc (i；j) from the network. The problem is to determine the minimal effort required to block all communications between the commander and his subordinates. Formulate this problem as a minimum cut problem.

6. [PhD Session only] Let D = (V； A; c) be a flow network with positive integer edge capacities, and f be a maximum s-t flow in D from a source s to a sink t. Denote m := |A| and n := |V|. Describe an O (nm²)-time algorithm for decomposing f into a convex combination of at most m integer maximum s-t flows in D.