Approximation algorithms for NP-complete problems on planar graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation algorithms for NP-complete problems on planar graphs

Full text

Pdf (1.98 MB)

Source

Journal of the ACM (JACM) archive
Volume 41 , Issue 1 (January 1994) table of contents

Pages: 153 - 180

Year of Publication: 1994

ISSN:0004-5411

Author

Brenda S. Baker

AT&T Bell Labs., Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 42, Downloads (12 Months): 382, Citation Count: 63

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174644.174650 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. Bar-Yehuda , S. Even, On approximating a vertex cover for planar graphs, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.303-309, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802205]
	2	Fran Berman , David Johnson , Tom Leighton , Peter W. Shor , Larry Snyder, Generalized planar matching, Journal of Algorithms, v.11 n.2, p.153-184, Jun. 1990 [doi>10.1016/0196-6774(90)90001-U]
	3	~BERMAN, F., LEIGHTON, F. T., AND SNYDER, L. 1982. Optimal tile salvage. VLSI Memo No. ~82-119. Massachusetts Institute of Technology, Cambridge, Mass.
	4	~BIENSTOCK, D., AND MONMA, C. L. 1990. On the complexity of embedding planar grapha to ~minimize certain distance measures. Al$orithmica 5, 93-109.
	5	~BuI, T. N., AND JONES, C. 1992. Finding optimal vertex separators in planar graphs with small ~separators. Comput. Sci. Dept., Pennsylvania State Univ., University Park, Pa.
	6	Thang Nguyen Bui , Andrew Peck, Partitioning planar graphs, SIAM Journal on Computing, v.21 n.2, p.203-215, April 1992 [doi>10.1137/0221016]
	7	~CHIBA, N., NISHIZEKI, T., AND SAITO, N. 198i, Applications of the Lipton and Tarjan's planar ~separator theorem. J. bzf. Proc. 4, 4, 203-207,
	8	~CHIBA, N., NISHiZEKI, T., AND SAITO, N. 1982, An approximation algorithm for the maximum ~independent set problem on planar graphs. SIAM J. Comput. 11, 4, 663-675.
	9	~COCKAYNE, E., GOODMAN, S., AND HEDETNIEMI, S. 1975. A linear algorithm for the domination ~number of a tree. Inf. Proc. Lett. 4, 41-44,
	10	~DJIDJEV, H. N. 1982. On the problem of partitioning planar graphs. SIAM J. Alg. Dzsc. Meth. 3, ~2, 229-240.
	11	DOLEV, D., LEIGHTON, F., AND TRICKEY, H. 1984. Planar embedding of planar graphs. In ~Advances m Computing Research. Vol. I{: ~ZSI Theory (F. Preparata, ed.) JAI Press, Inc., ~Greenwich, Ct., pp. 147-161.
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	~G^VRIL, F. 1972. Algorithms for minimum coloring, maximum clique, mimmum covering by ~cliques, and maximum independent set of a chordal graph. SIAMJ. Comput. l, 2, 180-187.
	14	~HARARY, F. 1971. Graph Theory. Addison-Wesley, Reading, Mass.
	15	~HOCHBAUM, D. S. 1981. Efficient bounds for the stable set, vertex cover and set packing ~problems. W.P. #50-80-81. GSIA, Carnegie-Mellon University, Pittsburgh, Pa., May.
	16	John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
	17	~LIPTON, R. J., AND TARJAN, R. E. 1979. A separator theorem for planar graphs. SIAM J. Appl. ~Math. 36, 2, 177-189.
	18	~LIPTON, R. J., AND TARJAN, R. E. 1980. Applications of a planar separator theorem. SIAM J. ~Comput. 9, 3, 615-627
	19	Sandra Lee Mitchell, Algorithms on trees and maximal outerplanar graphs: design, complexity analysis, and data structures study., 1977
	20	~MITCHELL, S. L., COCKAYNE, E. J., AND HEDETNIEMI, S. T. 1979. Linear algorithms on recursive ~representations of trees. J. Comput. Syst. Sci, 18, 76 85.
	21	~MITCHELL, S. L., AND HEDETNIEMI, S. T. 1975. Edge domination in trees. In Proceedings of the ~8th Southeastern Conference on Combinatoncs, Graph Theory, and Computtng (Winnipeg, ~Canada).
	22	~PAPADIMITR1OU, C. H., AND YANNAKAKIS, M. 1981. Worst-case ratios for planar graphs and the ~method of induction on faces. In Proceedings of tile 22nd Symposium on Foundatzons of ~Computer Sctence. IEEE, New York, pp. 358-363.
	23	K. Takamizawa , T. Nishizeki , N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, Journal of the ACM (JACM), v.29 n.3, p.623-641, July 1982 [doi>10.1145/322326.322328]
	24	~YANNAKAKIS, M., AND GAVRIL, F. 1980. Edge dominating sets in graphs. SiAM J. on Appl. Math. ~38, 3, 364-372.

CITED BY 63

	Shai Halevi , Robert Krauthgamer , Eyal Kushilevitz , Kobbi Nissim, Private approximation of NP-hard functions, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.550-559, July 2001, Hersonissos, Greece
	Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Sanjeev Khanna , Rajeev Motwani, Towards a syntactic characterization of PTAS, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.329-337, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Vilhelm Dahllöf , Peter Jonsson, An algorithm for counting maximum weighted independent sets and its applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.292-298, January 06-08, 2002, San Francisco, California
	John Kleinberg , Amit Kumar, Wavelength conversion in optical networks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 17-19, 1999, Baltimore, Maryland, United States
	Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-time approximation schemes for geometric graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.671-679, January 07-09, 2001, Washington, D.C., United States
	Geir Agnarsson , Magnús M. Halldórsson, Coloring powers of planar graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.654-662, January 09-11, 2000, San Francisco, California, United States
	Markus Frick , Martin Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM (JACM), v.48 n.6, p.1184-1206, November 2001
	Alberto Caprara , Romeo Rizzi, Packing triangles in bounded degree graphs, Information Processing Letters, v.84 n.4, p.175-180, 30 November 2002
	Vangelis T. Paschos, A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys (CSUR), v.29 n.2, p.171-209, June 1997
	Samir Khuller , Randeep Bhatia , Robert Pless, On local search and placement of meters in networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.319-328, January 09-11, 2000, San Francisco, California, United States
	Sergio Cabello , Marc van Kreveld, Approximation algorithms for aligning points, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003
	Richard E. Stearns , Harry B. Hunt, III, Exploiting structure in quantified formulas, Journal of Algorithms, v.43 n.2, p.220-263, May 2002
	Erik D. Demaine , MohammadTaghi Hajiaghayi, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Guohui Lin , Zhi-Zhong Chen , Tao Jiang , Jianjun Wen, The longest common subsequence problem for sequences with nested arc annotations, Journal of Computer and System Sciences, v.65 n.3, p.465-480, November 2002
	Jochen Alber , Michael R. Fellows , Rolf Niedermeier, Polynomial-time data reduction for dominating set, Journal of the ACM (JACM), v.51 n.3, p.363-384, May 2004
	Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, On the power assignment problem in radio networks, Mobile Networks and Applications, v.9 n.2, p.125-140, April 2004
	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, v.69 n.2, p.166-166, September 2004
	Jochen Alber , Jiří Fiala, Geometric separation and exact solutions for the parameterized independent set problem on disk graphs, Journal of Algorithms, v.52 n.2, p.134-151, August 2004
	Rajiv Gandhi , Samir Khuller , Aravind Srinivasan, Approximation algorithms for partial covering problems, Journal of Algorithms, v.53 n.1, p.55-84, October 2004
	Jochen Alber , Hongbing Fan , Michael R. Fellows , Henning Fernau , Rolf Niedermeier , Fran Rosamond , Ulrike Stege, A refined search tree technique for dominating set on planar graphs, Journal of Computer and System Sciences, v.71 n.4, p.385-405, November 2005
	Jochen Alber , Henning Fernau , Rolf Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Journal of Algorithms, v.52 n.1, p.26-56, July 2004
	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002
	Jochen Alber , Frederic Dorn , Rolf Niedermeier, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Discrete Applied Mathematics, v.145 n.2, p.219-231, 15 January 2005
	Erik D. Demaine , MohammadTaghi Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Transactions on Algorithms (TALG), v.1 n.1, p.33-47, July 2005
	Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
	Erik D. Demaine , MohammadTaghi Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Tomokazu Imamura , Kazuo Iwama, Approximating vertex cover on dense graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Virginia Vassilevska , Ryan Williams , Shan Leung Maverick Woo, Confronting hardness using a hybrid approach, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1-10, January 22-26, 2006, Miami, Florida
	Cristina Bazgan , Zsolt Tuza , Daniel Vanderpooten, Degree-constrained decompositions of graphs: bounded treewidth and planarity, Theoretical Computer Science, v.355 n.3, p.389-395, 14 April 2006
	Pankaj K. Agarwal , Nabil H. Mustafa, Independent set of intersection graphs of convex objects in 2D, Computational Geometry: Theory and Applications, v.34 n.2, p.83-95, May 2006
	Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001
	William Duckworth , Nicholas C. Wormald , Michele Zito, A PTAS for the sparsest 2-spanner of 4-connected planar triangulations, Journal of Discrete Algorithms, v.1 n.1, p.67-76, February 2003
	Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
	Quincy Wu , Chin Lung Lu , Richard Chia-Tung Lee, The approximability of the weighted Hamiltonian path completion problem on a tree, Theoretical Computer Science, v.341 n.1, p.385-397, 5 September 2005
	Cristina Bazgan , Bruno Escoffier , Vangelis Th. Paschos, Completeness in standard and differential approximation classes: poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, v.339 n.2, p.272-292, 12 June 2005
	Jianer Chen , Xiuzhen Huang , Iyad A. Kanj , Ge Xia, Polynomial time approximation schemes and parameterized complexity, Discrete Applied Mathematics, v.155 n.2, p.180-193, January, 2007
	C. Thach Nguyen , Jian Shen , Minmei Hou , Li Sheng , Webb Miller , Louxin Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.645-654, January 07-09, 2007, New Orleans, Louisiana
	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
	Chi Ma , Yuanyuan Yang , Zhenghao Zhang, Constructing battery-aware virtual backbones in wireless sensor networks, EURASIP Journal on Wireless Communications and Networking, v.2007 n.1, p.22-22, January 2007
	Jiong Guo , Rolf Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT News, v.38 n.1, March 2007
	Takehiro Ito , Akira Kato , Xiao Zhou , Takao Nishizeki, Algorithms for finding distance-edge-colorings of graphs, Journal of Discrete Algorithms, v.5 n.2, p.304-322, June, 2007
	Jianer Chen , Iyad A. Kanj , Ljubomir Perković , Eric Sedgwick , Ge Xia, Genus characterizes the complexity of certain graph problems: Some tight results, Journal of Computer and System Sciences, v.73 n.6, p.892-907, September, 2007
	MohammadTaghi Hajiaghayi , Naomi Nishimura, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Journal of Computer and System Sciences, v.73 n.5, p.755-768, August, 2007
	Erik D. Demaine , MohammadTaghi Hajiaghayi , Bojan Mohar, Approximation algorithms via contraction decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.278-287, January 07-09, 2007, New Orleans, Louisiana
	Piotr Indyk , Anastasios Sidiropoulos, Probabilistic embeddings of bounded genus graphs into planar graphs, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Paul Hunter , Stephan Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Theoretical Computer Science, v.399 n.3, p.206-219, June, 2008
	Vicky Choi, Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Information Processing, v.7 n.5, p.193-209, October 2008
	Costas Busch , Ryan LaFortune , Srikanta Tirthapura, Improved sparse covers for graphs excluding a fixed minor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Paul Hunter , Stephan Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.637-644, January 07-09, 2007, New Orleans, Louisiana
	Paz Carmi , Matthew J. Katz , Nissan Lev-Tov, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, Computational Geometry: Theory and Applications, v.39 n.3, p.209-218, April, 2008
	Meena Mahajan , Venkatesh Raman , Somnath Sikdar, Parameterizing above or below guaranteed values, Journal of Computer and System Sciences, v.75 n.2, p.137-153, February, 2009
	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
	Glencora Borradaile , James R. Lee , Anastasios Sidiropoulos, Randomly removing g handles at once, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Sylvain Guillemot , François Nicolas , Vincent Berry , Christophe Paul, On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems, Discrete Applied Mathematics, v.157 n.7, p.1555-1570, April, 2009
	Timothy M. Chan , Sariel Har-Peled, Approximation algorithms for maximum independent set of pseudo-disks, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	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
	Patrik Floréen , Joel Kaasinen , Petteri Kaski , Jukka Suomela, An optimal local approximation algorithm for max-min linear programs, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada