A near optimal algorithm for edge separators (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A near optimal algorithm for edge separators (preliminary version)

Full text

Pdf (536 KB)

Source

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

Montreal, Quebec, Canada

Pages: 1 - 8

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Fan R. K. Chung	Bell Communications Research, Morristown, New Jersey
S.-T. Yau	Harvard University, Cambridge, Massachusetts

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 43, Citation Count: 4

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/195058.195077 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	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	2	R. B. Boppana, Eigenvalues and graph bisection: An average-case analysis, FOCS 28 (1987) 280-285. Math. Comput. 19 (1965) 577- 593
	3	J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, (R. C. Gunning, ed.) Princeton Univ. Press (1970) 195-199.
	4	F. R. K. Chung and S.-T. Yau, Eigenvalues of graphs and Sobolev inequalities, preprint.
	5	James W. Demmel, Michael T. Heath and Henk A. van der Vorst, Acta Numerica 1993 ( A. Iserles ed.) Cambridge University Press, 111-197.
	6	W. E. Donath, A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Revelop. September 1973, 420-425
	7	M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput Sci. 1 (1976) 237- 267
	8	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]
	9	Bruce Hendrickson and Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, Sandia Report 1992.
	10	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	11	F. T. Leighton and Satish Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problem with applications to approximation algorithms, FOCS, 29 (1988) 422-431.
	12	R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177-189.
	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	Y. E. Nesterov and Arkadii Nemirovskii, Interior-Point Polynomial algorithms in Convex Programming, SIAM Studies in Applied Math. (1994).
	15	A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency, Wiley, New York (1983)
	16	J. Nocedal, Theory of algorithms for unconstrained optimization, Acta Numerica 1992 ( A. Iserles ed.) Cambridge University Press, 199-242.
	17	Satish Rao, Finding near optimal separators in planar graphs, FOCS, 28 (1987) 225-237.
	18	Shing-Tung Yau , Ya Yan Lu, Reducing the symmetric matrix eigenvalue problem to matrix multiplications, SIAM Journal on Scientific Computing, v.14 n.1, p.121-136, Jan. 1993 [doi>10.1137/0914008]

CITED BY 4

	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
	F. R. K. Chung , S.-T. Yau, Eigenvalues, flows and separators of graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.749, May 04-06, 1997, El Paso, Texas, United States
	Noga Alon , Nabil Kahale, A spectral technique for coloring random 3-colorable graphs (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.346-355, May 23-25, 1994, Montreal, Quebec, Canada
	Engineering graph clustering: Models and experimental evaluation, Journal of Experimental Algorithmics (JEA), 12, June 2008