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.
Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-qucosa-175057 |
Date | 13 November 2015 |
Creators | Helmberg, Christoph, Rocha, Israel, Schwerdtfeger, Uwe |
Contributors | Universidade Federal do Rio Grande do Sul, Instituto de Matematica, Technische Universität Chemnitz, Fakulät für Mathematik |
Publisher | Universitätsbibliothek Chemnitz |
Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
Language | English |
Detected Language | English |
Type | doc-type:preprint |
Format | application/pdf, text/plain, application/zip |
Page generated in 0.0045 seconds