Naoki Masuda, Tetsuya Fujie, Kazuo Murota
Studies in Computational Intelligence, 476 155-163, 2013 Peer-reviewed
The smallest positive eigenvalue of the Laplacian of a network is called the spectral gap and characterizes various dynamics on networks. We propose mathematical programming methods to maximize the spectral gap of a given network by removing a fixed number of nodes. We formulate relaxed versions of the original problem using semidefinite programming and apply them to example networks. © Springer-Verlag Berlin Heidelberg 2013.