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