[SOLVED] CSCE-629 Analysis of Algorithms Assignment # 5

1. A vertex v in an undirected graph G is an odd cycle transversal if every cycle of odd length in G contains the vertex v. Develop a linear-time algorithm for the following problem: given a graph G and a vertex v in G, decide if v is an odd cycle transversal.
2. Suppose that each class C_i has an enrollment r_i while each classroom R_j has a capacity c_j. A classroom R_j is “feasible” for a class C_i if c_j/2 ≤ r_i ≤ c_j. Develop an efficient algorithm that, on a set of classes (with enrollments given) and a set of classrooms (with capacities given), make a feasible assignment of the classes to the classrooms such that the as many classes as possible can get held starting at 9am on Monday.
3. Suppose that in addition to edge capacities, a flow network also has vertex capacities, i.e., each vertex v has a limit c(v) on how much flow can pass through v. Show how to transform a flow network G = (V,E) with vertex capacities into a flow network G⁰ = (V ⁰,E⁰) without vertex capacities, such that a maximum flow in G⁰ has the same value as a maximum flow in G.
4. (Textbook, page 731, Question 26.2-10) Show how to find a maximum flow in a flow network G = (V,E) by a sequence of at |E| augmenting paths. (Hint: determine the paths after finding the maximum flow.)

1