Detecting critical nodes in sparse graphs

Ashwin Arulselvan, Clayton W. Commander, Lily Elefteriadou, Panos M. Pardalos

Research output: Contribution to journalArticle

169 Citations (Scopus)

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 NPNP-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.
LanguageEnglish
Pages2193-2200
Number of pages8
JournalComputers & Operations Research
Volume36
Issue number7
DOIs
Publication statusPublished - Jul 2009
Externally publishedYes

Fingerprint

Sparse Graphs
Strategic planning
Heuristics
Integer programming
Vertex of a graph
Software packages
Linear programming
Telecommunication
Connectivity
Strategic Planning
Formulation
Integer Linear Programming
Graph in graph theory
Integer Programming
Telecommunications
Software Package
Military
Deletion
Optimal Solution
Node

Keywords

  • critical node detection
  • heuristics
  • integer linear programming

Cite this

Arulselvan, A., Commander, C. W., Elefteriadou, L., & Pardalos, P. M. (2009). Detecting critical nodes in sparse graphs. Computers & Operations Research, 36(7), 2193-2200. https://doi.org/10.1016/j.cor.2008.08.016
Arulselvan, Ashwin ; Commander, Clayton W. ; Elefteriadou, Lily ; Pardalos, Panos M. / Detecting critical nodes in sparse graphs. In: Computers & Operations Research. 2009 ; Vol. 36, No. 7. pp. 2193-2200.
@article{405b240173014957ad0e484a28afa19d,
title = "Detecting critical nodes in sparse graphs",
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 NPNP-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 node detection, heuristics, integer linear programming",
author = "Ashwin Arulselvan and Commander, {Clayton W.} and Lily Elefteriadou and Pardalos, {Panos M.}",
year = "2009",
month = "7",
doi = "10.1016/j.cor.2008.08.016",
language = "English",
volume = "36",
pages = "2193--2200",
journal = "Computers & Operations Research",
issn = "0305-0548",
number = "7",

}

Arulselvan, A, Commander, CW, Elefteriadou, L & Pardalos, PM 2009, 'Detecting critical nodes in sparse graphs' Computers & Operations Research, vol. 36, no. 7, pp. 2193-2200. https://doi.org/10.1016/j.cor.2008.08.016

Detecting critical nodes in sparse graphs. / Arulselvan, Ashwin; Commander, Clayton W.; Elefteriadou, Lily; Pardalos, Panos M.

In: Computers & Operations Research, Vol. 36, No. 7, 07.2009, p. 2193-2200.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Detecting critical nodes in sparse graphs

AU - Arulselvan, Ashwin

AU - Commander, Clayton W.

AU - Elefteriadou, Lily

AU - Pardalos, Panos M.

PY - 2009/7

Y1 - 2009/7

N2 - 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 NPNP-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.

AB - 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 NPNP-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.

KW - critical node detection

KW - heuristics

KW - integer linear programming

UR - http://www.sciencedirect.com/science/article/pii/S0305054808001494

U2 - 10.1016/j.cor.2008.08.016

DO - 10.1016/j.cor.2008.08.016

M3 - Article

VL - 36

SP - 2193

EP - 2200

JO - Computers & Operations Research

T2 - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

IS - 7

ER -