Optimization Online


Detecting Critical Nodes in Sparse Graphs

Ashwin Arulselvan(ashwin***at***ufl.edu)
Clayton Commander(clayton.commander***at***gmail.com)
Lily Elefteriadou(elefter***at***ce.ufl.edu)
Panos Pardalos(pardalos***at***ufl.edu)

Abstract: Identifying critical nodes in a graph is important to understand the structural characteristics and the connectivity properties of the network. In this paper, we focus on detecting critical nodes, or nodes whose deletion results in the minimum pair-wise connectivity among the remaining nodes. This problem, known as the CRITICAL NODE PROBLEM has applications in several fields including biomedicine, telecommunications, and military strategic planning. We show that the recognition version of the problem is N P -complete and derive a mathematical formulation based on integer linear programming. In addition, we propose a heuristic for the problem which exploits the combinatorial structure of the graph. The heuristic is then enhanced by the application of a local improvement method. A computational study is presented in which we apply the integer programming formulation and the heuristic to real and randomly generated data sets. For all instances tested, the heuristic is able to efficiently provide optimal solutions in a fraction of the time required by a commercial software package.

Keywords: Critical Nodes, Sparse Graphs, Combinatorial Optimization, Heuristics

Category 1: Combinatorial Optimization

Citation: Computers and Operations Research, in press, 2008.

Download: [PDF]

Entry Submitted: 09/28/2008
Entry Accepted: 09/28/2008
Entry Last Modified: 09/28/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society