(6 points) Given an undirected graph G = (V,E), your task is to orient every edge...

 

Transcribed Image Text:

(6 points) Given an undirected graph G = (V,E), your task is to orient every edge into a direc- tion such that the maximum outdegree of the directed graph obtained by such an orientation is minimized. For example, Figure 2b is an optimal way to orient the graph in Figure 2a. The out-degree of every vertex is upper bounded by 2 in Figure 2b. 6 4 5 (a) 9 6 8 4 (b) 3 8 9 1 Figure 2 (a) (4 points) Given an integer D, give a polynomial-time algorithm to determine whether it is possible to orient the edges such that the maximum out-degree of the oriented graph is at most D. (b) (2 points) Suppose the algorithm developed in question (a) has a running time of T(n, m). Develop an algorithm to compute an optimal orientation of G that minimizes the maximum out-degree. Your algorithm has to run in O(T(n, m) log n) time. (6 points) Given an undirected graph G = (V,E), your task is to orient every edge into a direc- tion such that the maximum outdegree of the directed graph obtained by such an orientation is minimized. For example, Figure 2b is an optimal way to orient the graph in Figure 2a. The out-degree of every vertex is upper bounded by 2 in Figure 2b. 6 4 5 (a) 9 6 8 4 (b) 3 8 9 1 Figure 2 (a) (4 points) Given an integer D, give a polynomial-time algorithm to determine whether it is possible to orient the edges such that the maximum out-degree of the oriented graph is at most D. (b) (2 points) Suppose the algorithm developed in question (a) has a running time of T(n, m). Develop an algorithm to compute an optimal orientation of G that minimizes the maximum out-degree. Your algorithm has to run in O(T(n, m) log n) time.