Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

DOI10.1007/s10107-010-0344-zzbMath1232.05124MaRDI QIDQ662288

Christoph Helmberg, Susanna Reiss, Frank Göring

Publication date: 22 February 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0344-z

zbMATH Keywords

Semidefinite programming; Graph partitioning; Eigenvalue optimization; Embedding; Spectral graph theory; Tree-width

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C22: Semidefinite programming

05C10: Planar graphs; geometric and topological aspects of graph theory

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C40: Connectivity

Related Items

Combinatorial Algorithms for Minimizing the Maximum Laplacian and Signless Laplacian Eigenvalues of Weighted Graphs, Comparison of Metric Spectral Gaps, Spectral representations of vertex transitive graphs, Archimedean solids and finite Coxeter groups, A new graph parameter related to bounded rank positive semidefinite matrix completions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds on graph eigenvalues. I
• Bounds on the (Laplacian) spectral radius of graphs
• Realizability of graphs
• On the relation between two minor-monotone graph parameters
• Expanding and forwarding
• Consistency of spectral clustering
• Probability theory. A comprehensive course.
• Several sharp upper bounds for the largest Laplacian eigenvalue of a graph
• Generic global rigidity
• The rotational dimension of a graph
• Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Embedded in the Shadow of the Separator
• Absolute algebraic connectivity of trees
• The Molecule Problem: Exploiting Structure in Global Optimization
• Minimizing Effective Resistance of a Graph
• Handbook of semidefinite programming. Theory, algorithms, and applications