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)

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

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)

Cited In (28)

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

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)