Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Christoph Helmberg, Israel Rocha, Uwe Schwerdtfeger: A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs

Christoph Helmberg, Israel Rocha, Uwe Schwerdtfeger: A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs


Author(s):
Christoph Helmberg
Israel Rocha
Uwe Schwerdtfeger
Title:
Christoph Helmberg, Israel Rocha, Uwe Schwerdtfeger: A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 12, 2015
Mathematics Subject Classification:
    05C05 []
    05C10 []
    05C50 []
    05C85 []
    90C22 []
    90C35 []
Abstract:
We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.
Keywords:
bipartite graph, tree, weighted Laplacian matrix, graph embedding
Language:
English
Publication time:
07/2015

Presseartikel