On the Quality of Spectral Separators

DOI10.1137/S0895479896312262zbMATH Open0905.05050MaRDI QIDQ4389101FDOQ4389101

Authors Stephen Guattery, Gary L. Miller 

Publication date 11 May 1998

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

graph partitioningspectral partitioninggraph eigenvalues and eigenvectors

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Publication:4886053
• Spectral partitioning works: planar graphs and finite element meshes
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Spectral bisection with two eigenvectors

Cited in

(29)

• Separability and window length in singular spectrum analysis
• On the maximal error of spectral approximation of graph bisection
• A spectral method to detect community structure based on distance modularity matrix
• scientific article; zbMATH DE number 910879 (Why is no real title available?)
• Consistency of spectral clustering
• Graph clustering
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Improvements on spectral bisection
• An attempt to separate \(A \rightarrow B\) process spectra. Separation by minimum overlapping method SEMILAM
• New abilities and limitations of spectral graph bisection
• A new lower bound on the size of the smallest vertex separator of a graph
• Improved row-by-row method for binary quadratic optimization problems
• A spectral approach to bandwidth and separator problems in graphs
• Optimality of spectral clustering in the Gaussian mixture model
• Spectral bisection with two eigenvectors
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Diffuse interface models on graphs for classification of high dimensional data
• Signed graph partitioning by spectral rounding
• Combinatorial characterization of the null spaces of symmetric H-matrices
• Spectral partitioning works: planar graphs and finite element meshes
• A note on edge-based graph partitioning and its linear algebraic structure
• Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation
• Approximating spectral clustering via sampling: a review
• On the eigenvectors of \(p\)-Laplacian
• On the Laplacian Eigenvalues of G_n,p
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Graph Laplacians, nodal domains, and hyperplane arrangements
• Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images
• Effective Resistance Preserving Directed Graph Symmetrization

This page was built for publication: On the Quality of Spectral Separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389101)