Fan R. K. Chung
- 1.Noga Alon, Eigenvalues and expanders, Combinatorica 6 (1986) 83-86. Google Scholar
Digital Library
- 2.R. B. Boppana, Eigenvalues and graph bisection: An average-case analysis, FOCS 28 (1987) 280-285. Math. Comput. 19 (1965) 577- 593Google Scholar
- 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.Google Scholar
- 4.F. R. K. Chung and S.-T. Yau, Eigenvalues of graphs and Sobolev inequalities, preprint.Google Scholar
- 5.James W. Demmel, Michael T. Heath and Henk A. van der Vorst, Acta Numerica 1993 ( A. Iserles ed.) Cambridge University Press, 111-197.Google Scholar
- 6.W. E. Donath, A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Revelop. September 1973, 420-425Google ScholarDigital Library
- 7.M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput Sci. 1 (1976) 237- 267Google ScholarCross Ref
- 8.j. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separator theorem for graphs with bounded genus, J. Algorithms 5 (1984) 391- 407. Google ScholarDigital Library
- 9.Bruce Hendrickson and Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, Sandia Report 1992.Google Scholar
- 10.M. Jerrum and A. Sinclair, Approximating the permanent, SIAM J. Computing 18 (1989). 1149-1178. Google ScholarDigital Library
- 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.Google Scholar
- 12.R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177-189.Google ScholarCross Ref
- 13.B. Mohar, Isoperimetric number of graphs,J. of Comb. Theory (B) 47 (1989), 274-291. Google ScholarDigital Library
- 14.Y. E. Nesterov and Arkadii Nemirovskii, Interior-Point Polynomial algorithms in Convex Programming, SIAM Studies in Applied Math. (1994).Google Scholar
- 15.A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency, Wiley, New York (1983)Google Scholar
- 16.J. Nocedal, Theory of algorithms for unconstrained optimization, Acta Numerica 1992 ( A. Iserles ed.) Cambridge University Press, 199-242.Google Scholar
- 17.Satish Rao, Finding near optimal separators in planar graphs, FOCS, 28 (1987) 225-237.Google Scholar
- 18.S. T. Yau and Y. Y. Lu, Reducing the symmetric matrix eigenvalue problem to matrix multiplications, SIAM J. Scientific Computing 14 (1993) 121-136 Google ScholarDigital Library
Index Terms
- A near optimal algorithm for edge separators (preliminary version)
Recommendations
Finding near optimal separators in planar graphs
SFCS '87: Proceedings of the 28th Annual Symposium on Foundations of Computer ScienceA k-ratio edge separator is a set of edges which separates a weighted graph into two disconnected sets of components neither of which contains more than k-1/k of the original graph's weight. An optimal quotient separator is an edge separator where the ...
Edge separators for quasi-binary trees
One wishes to remove k - 1 edges of a vertex-weighted tree T such that the weights of the k induced connected components are approximately the same. How well can one do it? In this paper, we investigate such k -separators for quasi-binary trees. We show ...
Homogeneous sets, clique-separators, critical graphs, and optimal χ-binding functions
AbstractGiven a set H of graphs, let f H ⋆ : N > 0 → N > 0 be the optimal χ-binding function of the class of H-free graphs, that is, f H ⋆ ( ω ) = max { χ ( G ) : G is H -free, ω ( G ) = ω } . In this paper, we combine the two decomposition ...
Comments