A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph

DOI10.1137/20M1382118zbMath1492.65104OpenAlexW4220887533MaRDI QIDQ5862814

Yongyan Guo, Gang Wu

Publication date: 10 March 2022

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

Full work available at URL: https://doi.org/10.1137/20m1382118

zbMATH Keywords

spectral methodgraph partitioningLaplacian matrixvertex separatorseparator minimization

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Uses Software

• CONTEST
• testmatrix

Cites Work

• Finding good approximate vertex and edge partitions is NP-hard
• Isoperimetric numbers of graphs
• Linear Algebra Tools for Data Mining
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Parallel Algorithms for Sparse Linear Systems
• On the Quality of Spectral Separators
• Spectral partitioning with blends of eigenvectors
• Lower Bounds for the Partitioning of Graphs

This page was built for publication: A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph