Finding minimum-quotient cuts in planar graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding minimum-quotient cuts in planar graphs

Full text

Pdf (1.06 MB)

Source

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

San Diego, California, United States

Pages: 766 - 775

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

James K. Park
Cynthia A. Phillips

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 37, Citation Count: 5

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/167088.167284 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	B. Baker. Approximation algorithms for NP- complete problems on planar graphs, in Proceedings of the 2#th Annual IEEE Symposzum on Foundations of Computer Science, pages 265-273, 1983.
	2	S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems, journal of Computer and System Sczences, 28(2):300-343, 1984.
	3	Thang Nguyen Bui , Curt Jones, Finding good approximate vertex and edge partitions is NP-hard, Information Processing Letters, v.42 n.3, p.153-159, May 25, 1992 [doi>10.1016/0020-0190(92)90140-Q]
	4	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]
	5	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
	6	M. R. Garey, D. S. Johnson, and L. J. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237-267, 1976.
	7	R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexzty of Computer Computations, pages 85-103. Plenum Press, New York, NY, 1972.
	8	F. T. Leighton and S. B. Rao. An approximate max-flow rain-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedzngs of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 422-431, 1988.
	9	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979.
	10	R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9:615-627, 1980.
	11	N. Megiddo. Combinatorial optimization with rational objective functions. Mathematic8 of Operatzons Research, 4(4):414-424, 1979.
	12	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	13	B. Mohar, Isoperimetric numbers of graphs, Journal of Combinatorial Theory Series B, v.47 n.3, p.274-291, Dec. 1989 [doi>10.1016/0095-8956(89)90029-4]
	14	S. B. Rao. Finding near optimal separators in planar graphs. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 225-237, 1987.
	15	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129735]

CITED BY 5

	Reuven Bar-Yehuda , Craig Gotsman, Time/space tradeoffs for polygon mesh rendering, ACM Transactions on Graphics (TOG), v.15 n.2, p.141-152, April 1996
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Matin Hashemi , Soheil Ghiasi, Throughput-driven synthesis of embedded software for pipelined execution on multicore architectures, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.2, p.1-35, January 2009