6) (10+20) The following theorem holds for any planar graph: There is a set of 0(n)...

 

Transcribed Image Text:

6) (10+20) The following theorem holds for any planar graph: There is a set of 0(n) vertices (called the separator set) whose removal from a n-vertex planar graph partitions the graph into disjoint subgraphs each having at most 2n/3 vertices. Given a n vertex planar graph, assume that such a separator set can be computed in 0 (n) time. a) Given an unweighted planar bipartite graph, use the planar separator theorem to design a divide-and-conquer algorithm for computing the maximum cardinality matching. This algorithm should take O(n.5) time. b) Give a divide and conquer algorithm to compute minimum-cost matching in a weighted planar bipartite graph. The execution time of this algorithm should be 0 (n.5 logn) time. (You can assume that this graph has a perfect matching and that all the edge costs are positive). 6) (10+20) The following theorem holds for any planar graph: There is a set of 0(n) vertices (called the separator set) whose removal from a n-vertex planar graph partitions the graph into disjoint subgraphs each having at most 2n/3 vertices. Given a n vertex planar graph, assume that such a separator set can be computed in 0 (n) time. a) Given an unweighted planar bipartite graph, use the planar separator theorem to design a divide-and-conquer algorithm for computing the maximum cardinality matching. This algorithm should take O(n.5) time. b) Give a divide and conquer algorithm to compute minimum-cost matching in a weighted planar bipartite graph. The execution time of this algorithm should be 0 (n.5 logn) time. (You can assume that this graph has a perfect matching and that all the edge costs are positive).