Efficient Algorithms for k -Terminal Cuts on Planar Graphs

摘要: The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel distributed computing, VLSI circuit design, networking. In this paper we present two new approximation exact algorithms for on an n-vertex undirected weighted planar graph G. For the case when k terminals are covered by boundaries m > 1 faces G, we give a min{O(n 2 log n logm), O(m 2 n 1.5 log2 + k n)} time algorithm with (2–2/k)-approximation ratio (clearly, \le k). all boundary one face we give an O(n k3 (n n)k 2) algorithm, or linear if = 3, computing optimal k-terminal cut. Our based interesting observations improve previous when they applied to planar graphs. To our best knowledge, no specifically for solving graphs were known before. (2–2/k)-approximation algorithm Dahlhaus et al. (for general graphs) takes O(k n) Our approximation runs faster than that at least O(k/logm) factor (m