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

Description

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.

Links & Downloads

1. urn:nbn:de:bsz:ch1-qucosa-175057
2. 1614-8835
3. https://monarch.qucosa.de/id/qucosa%3A20293
4. https://monarch.qucosa.de/api/qucosa%3A20293/attachment/ATT-0/
5. https://monarch.qucosa.de/api/qucosa%3A20293/attachment/ATT-1/

Tags

info:eu-repo/classification/ddc/510

ddc:510

bipartiter Graph; Baum

Additional Fields

Identifer	oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:20293
Date	13 November 2015
Creators	Helmberg, Christoph, Rocha, Israel, Schwerdtfeger, Uwe
Contributors	Universidade Federal do Rio Grande do Sul
Publisher	Technische Universität Chemnitz
Source Sets	Hochschulschriftenserver (HSSS) der SLUB Dresden
Language	English
Detected Language	English
Type	doc-type:preprint, info:eu-repo/semantics/preprint, doc-type:Text
Rights	info:eu-repo/semantics/openAccess