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: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 |
Page generated in 0.0098 seconds