Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

DOI10.1007/s10107-010-0344-zzbMath1232.05124OpenAlexW2148597446MaRDI 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 programmingGraph partitioningEigenvalue optimizationEmbeddingSpectral graph theoryTree-width

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) Connectivity (05C40)

Related Items (4)

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

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

This page was built for publication: Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian