Maximum algebraic connectivity augmentation is NP-hard |
| |
| Authors: | Damon Mosk-Aoyama |
| |
| Affiliation: | Department of Computer Science, Stanford University, Gates Building, Room 460, 353 Serra Mall, Stanford, CA 94305, USA |
| |
| Abstract: | The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard. |
| |
| Keywords: | Algebraic connectivity Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
