A separator theorem for graphs with an excluded minor and its applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A separator theorem for graphs with an excluded minor and its applications

Full text

Pdf (531 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 293 - 299

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

N. Alon	IBM Almaden Research Center, San Jose, CA and Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel
P. Seymour	BellCore, 445 South St., Morristown, NJ
R. Thomas	School of Mathematics, Georgia Institute of Technology, Atlanta, GA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 62, Citation Count: 25

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/100216.100254 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	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	2	Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
	3	John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
	4	A. V. Kostochka, A lower bound for the Hadwiger number of a graph as a function of the average degree of its vertices, Diskret. Analiz. Novosibirsk 38(1982), 37-58. (In Russian).
	5	C. E. Leiserson, Area efficient graph layouts (for VLSO, Proc. 21 FOCS (1980), 270-281.
	6	R. J. Lipton, D. J. Rose and R. E. Tarjan, Generalized nested dissection, SIAM J. Numer. Anal., 16(1979), 177-189.
	7	R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36(1979), 177-189.
	8	R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, Proc. 18th FOCS (1977), 162-170.
	9	R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, SIAM J. Comput. 9(1980), 615-627.
	10	P. D. Seymour and R. Thomas, Graph searching, and a minimax theorem for tree-width, to appear.
	11	C. Thomassen, The graph genus problem is NP-complete, Journal of Algorithms, v.10 n.4, p.568-576, Dec. 1989 [doi>10.1016/0196-6774(89)90006-0]
	12	A. G. Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95(1984), 261-265.
	13	Arnie Rosenthal, Nonserial dynamic programming is optimal, Proceedings of the ninth annual ACM symposium on Theory of computing, p.98-105, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803399]

CITED BY 25

	Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
	Bruce A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.221-228, May 04-06, 1992, Victoria, British Columbia, Canada
	Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
	Christos Kaklamanis , Danny Krizanc , Satish Rao, New graph decompositions and fast emulations in hypercubes and butterflies, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.325-334, June 30-July 02, 1993, Velen, Germany
	Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997
	David R. Karger, Using random sampling to find maximum flows in uncapacitated undirected graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.240-249, May 04-06, 1997, El Paso, Texas, United States
	Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004
	Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada
	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada
	L. Sunil Chandran , C. R. Subramanian, A spectral lower bound for the treewidth of a graph and its consequences, Information Processing Letters, v.87 n.4, p.195-200, 31 August 2003
	Jochen Alber , Henning Fernau , Rolf Niedermeier, Graph separators: a parameterized view, Journal of Computer and System Sciences, v.67 n.4, p.808-832, December 2003
	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
	Keith D. Gremban , Gary L. Miller , Shang-Hua Teng, Moments of inertia and graph separators, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.452-461, January 23-25, 1994, Arlington, Virginia, United States
	Eli Ben-Sasson, Hard examples for the bounded depth Frege proof system, Computational Complexity, v.11 n.3/4, p.109-136, March 2003
	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
	Eli Ben-Sasson, Hard examples for bounded depth frege, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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 , 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
	Vilhelm Dahllöf , Peter Jonsson , Magnus Wahlström, Counting models for 2SAT and 3SAT formulae, Theoretical Computer Science, v.332 n.1-3, p.265-291, 28 February 2005
	Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	David Steurer, Tight bounds for the Min-Max boundary decomposition cost of weighted graphs, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Artur Czumaj , Christian Sohler, On testable properties in bounded degree graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.494-501, January 07-09, 2007, New Orleans, Louisiana
	Noga Alon , Andrzej Lingas , Martin Wahlen, Approximating the maximum clique minor and some subgraph homeomorphism problems, Theoretical Computer Science, v.374 n.1-3, p.149-158, April, 2007
	Keith Edwards, Detachments of Complete Graphs, Combinatorics, Probability and Computing, v.14 n.3, p.275-310, May 2005
	Jaroslav Nešetřil , Patrice Ossona de Mendez, Grad and classes with bounded expansion II. Algorithmic aspects, European Journal of Combinatorics, v.29 n.3, p.777-791, April, 2008