Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs

Siqian Shen, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

51 Scopus citations

Abstract

We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of network interdiction and graph theory research and are relevant to several practical optimization problems. The two different connectivity metrics that we consider regard the number of maximal connected components (which we attempt to maximize) and the largest component size (which we attempt to minimize). We develop optimal polynomial-time dynamic programming algorithms for solving these problems on tree structures and on series-parallel graphs, corresponding to each graph-connectivity metric. We also extend our discussion by considering node deletion costs, node weights, and solving the problems on generalizations of tree structures. Finally, we demonstrate the computational efficacy of our approach on randomly generated graph instances.

Original languageEnglish (US)
Pages (from-to)103-119
Number of pages17
JournalNetworks
Volume60
Issue number2
DOIs
StatePublished - Sep 1 2012
Externally publishedYes

Keywords

  • critical node problem
  • dynamic programming
  • polynomial-time algorithm
  • series-parallel graph
  • tree

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs'. Together they form a unique fingerprint.

Cite this