- AutorIn
- Prof. Dr. Christoph Helmberg
- Dr. Israel Rocha
- Dr. Uwe Schwerdtfeger
- Titel
- A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:ch1-qucosa-175057
- ISSN
- 1614-8835
- Abstract (EN)
- 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.
- Andere Ausgabe
- Link: http://www.tu-chemnitz.de/mathematik/preprint/
- Freie Schlagwörter (DE)
- Bipartiter Graph, Baum, gewichtete Laplace Matrix, Einbettung von Graphen
- Freie Schlagwörter (EN)
- bipartite graph, tree, weighted Laplacian matrix, graph embedding
- Klassifikation (DDC)
- 510
- Normschlagwörter (GND)
- bipartiter Graph, Baum
- Herausgeber (Institution)
- Universidade Federal do Rio Grande do Sul
- Publizierende Institution
- Technische Universität Chemnitz, Chemnitz
- URN Qucosa
- urn:nbn:de:bsz:ch1-qucosa-175057
- Veröffentlichungsdatum Qucosa
- 13.11.2015
- Dokumenttyp
- Preprint
- Sprache des Dokumentes
- Englisch