Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Göring, Frank; Helmberg, Christoph; Wappler, Markus : Embedded in the Shadow of the Separator

Göring, Frank ; Helmberg, Christoph ; Wappler, Markus : Embedded in the Shadow of the Separator


Author(s):
Göring, Frank
Helmberg, Christoph
Wappler, Markus
Title:
Embedded in the Shadow of the Separator
Electronic source:
application/pdf
application/postscript
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 12, 2005
Mathematics Subject Classification:
05C50 [ Graphs and matrices ]
90C22 [ Semidefinite programming ]
Abstract:
We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and exploiting optimality conditions we show that the problem is equivalent to finding an embedding of the $n$ nodes in $n-$space so that their barycenter is at the origin, the distance between adjacent nodes is bounded by one and the nodes are spread as much as possible (the sum of the squared norms is maximized). For connected graphs we prove that for any separator in the graph, at least one of the two separated node sets is embedded in the shadow (with the origin being the light source) of the convex hull of the separator. In particular, the barycenters of partitions induced by separators are separated by the affine subspace spanned by the nodes of the separator. Furthermore, we show that there always exists an optimal embedding whose dimension is bounded by the tree width of the graph plus one.
Keywords:
spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, graph partitioning, tree-width
Language:
English
Publication time:
9 / 2005

Presseartikel

  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …

  • Wahlzeit an der Universität

    Wahlvorschläge für Organe und Ämter an der TU Chemnitz können bis zum 23. Oktober 2017 eingereicht werden – Briefwahlanträge sind bis 27. Oktober 2017 zu stellen …