Embedded in the Shadow of the Separator

DOI10.1137/050639430zbMath1169.05347OpenAlexW2161247714MaRDI QIDQ3608992

Frank Göring, Markus Wappler, Christoph Helmberg

Publication date: 6 March 2009

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b5b18682e0535a8d420d2869d765ea242fe967ba

zbMATH Keywords

embeddingeigenvalue optimizationsemidefinite programminggraph partitioningtree widthspectral graph theory

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (13)

Connectedness of users-items networks and recommender systems ⋮ The rotational dimension of a graph ⋮ Finding graph embeddings by incremental low-rank semidefinite programming ⋮ Spectral representations of vertex transitive graphs, Archimedean solids and finite Coxeter groups ⋮ Embedding and the rotational dimension of a graph containing a clique ⋮ Absolute algebraic connectivity of double brooms and trees ⋮ Projected primal-dual gradient flow of augmented Lagrangian with application to distributed maximization of the algebraic connectivity of a network ⋮ Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian ⋮ Comparison of Metric Spectral Gaps ⋮ A new graph parameter related to bounded rank positive semidefinite matrix completions ⋮ A note on Fiedler vectors interpreted as graph realizations ⋮ Consensus control for linear systems with optimal energy cost ⋮ Combinatorial Algorithms for Minimizing the Maximum Laplacian and Signless Laplacian Eigenvalues of Weighted Graphs

Uses Software

• SeDuMi

This page was built for publication: Embedded in the Shadow of the Separator