×

A polynomial-time approximation scheme for planar multiway cut. (English) Zbl 1422.68294

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 639-655 (2012).

MSC:

68W25 Approximation algorithms
05C40 Connectivity
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms

Citations:

Zbl 0809.68075
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650] · Zbl 0807.68067
[2] MohammadHossein Bateni , MohammadTaghi Hajiaghayi , Dániel Marx, Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth, Proceedings of the 42nd ACM symposium on Theory of computing, June 05-08, 2010, Cambridge, Massachusetts, USA [doi>10.1145/1806689.1806720] · Zbl 1293.68308
[3] Cédric Bentz, Note: A simple algorithm for multicuts in planar graphs with outer terminals, Discrete Applied Mathematics, v.157 n.8, p.1959-1964, April, 2009 [doi>10.1016/j.dam.2008.11.010] · Zbl 1197.05140 · doi:10.1016/j.dam.2008.11.010
[4] Glencora Borradaile , Claire Kenyon-Mathieu , Philip Klein, A polynomial-time approximation scheme for Steiner tree in planar graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1285-1294, January 07-09, 2007, New Orleans, Louisiana · Zbl 1302.05178
[5] Glencora Borradaile , Philip N. Klein , Claire Mathieu, Steiner tree in planar graphs: an O(n log n) approximation scheme with singly-exponential dependence on epsilon, Proceedings of the 10th international conference on Algorithms and Data Structures, August 15-17, 2007, Halifax, Canada · Zbl 1209.68633
[6] Glencora Borradaile , Philip N. Klein , Claire Mathieu, A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.115-124, October 25-28, 2008 [doi>10.1109/FOCS.2008.59] · Zbl 1398.68661 · doi:10.1109/FOCS.2008.59
[7] Glencora Borradaile , Philip Klein , Claire Mathieu, An O(n log n) approximation scheme for Steiner tree in planar graphs, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-31, July 2009 [doi>10.1145/1541885.1541892] · Zbl 1300.05294
[8] Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for multiway cut, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.48-52, May 24-26, 1998, Dallas, Texas, USA [doi>10.1145/276698.276711] · Zbl 1028.68220
[9] Danny Z. Chen , Xiaodong Wu, Efficient Algorithms for k-Terminal Cuts on Planar Graphs, Proceedings of the 12th International Symposium on Algorithms and Computation, December 19-21, 2001, Christchurch, New Zealand [doi>10.1007/3-540-45678-3_29] · Zbl 1077.68722 · doi:10.1007/3-540-45678-3_29
[10] William H. Cunningham , Lawrence Tang, Optimal 3-Terminal Cuts and Linear Programming, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.114-125, June 09-11, 1999 · Zbl 0948.90159
[11] E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297] · Zbl 0809.68075 · doi:10.1137/S0097539792225297
[12] D. Eppstein, Subgraph isomorphism in planar graphs and related problems, Journal of Graph Algorithms and Applications, 3 (1999), pp. 1-27. · Zbl 0949.05055
[13] Ranel E. Erickson , Clyde L. Monma , Arthur F. Veinott, Jr., Send-and-split method for minimum-concave-cost network flows, Mathematics of Operations Research, v.12 n.4, p.634-664, Nov. 1987 [doi>10.1287/moor.12.4.634] · Zbl 0667.90036 · doi:10.1287/moor.12.4.634
[14] David Hartvigsen, The planar multiterminal cut problem, Discrete Applied Mathematics, v.85 n.3, p.203-222, July 22, 1998 [doi>10.1016/S0166-218X(98)00036-5] · Zbl 0908.90259 · doi:10.1016/S0166-218X(98)00036-5
[15] T. C. Hu, Integer Programming and Network Flows, Addison-Wesley, 1969. · Zbl 0197.45701
[16] Yoko Kamidoi , Noriyoshi Yoshida , Hiroshi Nagamochi, A Deterministic Algorithm for Finding All Minimum \(k\)-Way Cuts, SIAM Journal on Computing, v.36 n.5, p.1329-1341, December 2006 [doi>10.1137/050631616] · Zbl 1124.05083 · doi:10.1137/050631616
[17] David R. Karger , Philip Klein , Cliff Stein , Mikkel Thorup , Neal E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.668-678, May 01-04, 1999, Atlanta, Georgia, USA [doi>10.1145/301250.301430] · Zbl 1345.90095
[18] Philip N. Klein, A linear-time approximation scheme for planar weighted TSP, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 23-25, 2005 [doi>10.1109/SFCS.2005.7] · doi:10.1109/SFCS.2005.7
[19] Philip N. Klein, A subset spanner for Planar graphs,: with application to subset TSP, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132620] · Zbl 1301.05335
[20] Philip N. Klein, A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights, SIAM Journal on Computing, v.37 n.6, p.1926-1952, March 2008 [doi>10.1137/060649562] · Zbl 1155.68090 · doi:10.1137/060649562
[21] James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, USA [doi>10.1145/167088.167284] · Zbl 1310.05203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.