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.0022 seconds