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:qucosa:20293
Date13 November 2015
CreatorsHelmberg, Christoph, Rocha, Israel, Schwerdtfeger, Uwe
ContributorsUniversidade Federal do Rio Grande do Sul
PublisherTechnische Universität Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:preprint, info:eu-repo/semantics/preprint, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0021 seconds