| Article ID: | iaor20102913 |
| Volume: | 36 |
| Issue: | 6 |
| Start Page Number: | 677 |
| End Page Number: | 679 |
| Publication Date: | Nov 2008 |
| Journal: | Operations Research Letters |
| Authors: | Mosk-Aoyama Damon |
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.