A spectral approach to bandwidth and separator problems in graphs

DOI10.1080/03081089508818381zbMath0832.05093OpenAlexW1995658164MaRDI QIDQ4853927

Svatopluk Poljak, Bojan Mohar, Franz Rendl, Christoph Helmberg

Publication date: 11 December 1995

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03081089508818381

zbMATH Keywords

bandwidtheigenvaluesnonlinear optimizationboundsLaplacianvertex separatorspectral approachlargest common subgraphseparator problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Copositive and semidefinite relaxations of the quadratic assignment problem, Matrix Relaxations in Combinatorial Optimization, On semidefinite programming bounds for graph bandwidth, Lower bounds for the quadratic assignment problem via triangle decompositions, Semidefinite relaxations of ordering problems, Semidefinite approximations for quadratic programs over orthogonal matrices, Lower bounds for the bandwidth problem, Bounds on special subsets in graphs, eigenvalues and association schemes, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A preconditioned iterative interior point approach to the conic bundle subproblem, Continuation methods for approximate large scale object sequencing, The MIN-cut and vertex separator problem, The toughness of Kneser graphs, SDP Relaxations for Some Combinatorial Optimization Problems, On a conjecture of Brouwer involving the connectivity of strongly regular graphs, On the bandwidth of the Kneser graph

Cites Work

• Optimal linear labelings and eigenvalues of graphs
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• The bandwidth problem for graphs and matrices—a survey
• On the Sum of the Largest Eigenvalues of a Symmetric Matrix
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Laplace eigenvalues and bandwidth‐type invariants of graphs