A Simple Algorithm for the Planar Multiway Cut Problem

Dalhaus, 1994, The complexity of the multiway cuts, SIAM J. Comput., 23, 864, 10.1137/S0097539792225297 O. Goldschmidt, Deterministic and Probabilistic Aspects of the k-Way Cut Problem, Ph.D. Dissertation, U.C. Berkeley, 1988. Goldschmidt, 1988, Polynomial algorithm for the k-way cut problem O. Goldschmidt, and, D. S. Hochbaum, A Polynomial Algorithm for the k-Way Cut Problem for Fixed k, Unpublished paper, 1991. Goldschmidt, 1990, Asymptotically optimal linear algorithm for the minimum k-way cut in a random graph, SIAM J. Discrete Math., 3, 58, 10.1137/0403007 He, 1991, An improved algorithm for the planar 3-way cut problem, J. Algorithms, 12, 23, 10.1016/0196-6774(91)90021-P Hochbaum, 1985, An O(|V|2) algorithm for the planar 3-way cut problem, SIAM J. Algebraic Discrete Math., 6, 707, 10.1137/0606068 D. S. Hochbaum, and, L. Tsai, A Greedy Algorithm for the 3-Way Cut Problem and Its Worse Case Bound, Technical report, IP-318, Economic Theory and Econometrics, U. C. Berkeley, 1983. H. S. Wang, On Minimum-Fold Cuts in Networks, Ph.D. Dissertation, University of Texas at Arlington, 1990. Hopcroft, 1973, Algorithm 447: Efficient algorithms for graph manipulation, Comm. Assoc. Comput. Mach., 16, 327 Yeh, 1992, A polynomial algorithm for the planar k-way cut problem Stone, 1997, Multiprocessor scheduling with the aid of network flow algorithms, IEEE Trans. Software Engrg., 3, 85