A spectral approach to bandwidth and separator problems in graphs |
| |
| Authors: | Christoph Helmberg Franz Rendl Bojan Mohar Svatopluk Poljak |
| |
| Affiliation: | a Department of Mathematics, University of Technology Graz, Graz, Kopernikusgasse 24, Austriab Department of Mathematics, University of Ljubijana, Ljubljana, Jadranska 19, Sloveniac Faculty of Mathematics and Informatic, University of Passau, Passau, Innstrassc 33, Germany |
| |
| Abstract: | Lower bounds on the bandwidth, the size of a vertex separator of general undirected graphs, and the largest common subgraph of two undirected (weighted) graphs are obtained. The bounds are based on a projection technique developed for the quadratic assignment problem, and once more demonstrate the importance of the extreme eigenvalues of the Laplacian. They will be shown to be strict for certain classes of graphs and compare favourably to bounds already known in literature. further improvement is gained by applying nonlinear optimization methods. |
| |
| Keywords: | |
| 本文献已被 InformaWorld 等数据库收录！ |
|
