Return to search

A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-qucosa-175057
Date13 November 2015
CreatorsHelmberg, Christoph, Rocha, Israel, Schwerdtfeger, Uwe
ContributorsUniversidade Federal do Rio Grande do Sul, Instituto de Matematica, Technische Universität Chemnitz, Fakulät für Mathematik
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:preprint
Formatapplication/pdf, text/plain, application/zip

Page generated in 0.002 seconds