Exact interdiction models and algorithms for disconnecting networks via node deletions

Siqian Shen, J. Cole Smith, Roshan Goli

Research output: Contribution to journalArticle

47 Scopus citations

Abstract

This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected components (which we attempt to maximize), the largest component size (which we attempt to minimize), and the minimum cost required to reconnect the graph after the nodes are deleted (which we attempt to maximize). We formulate each problem as a mixed-integer program, and then study valid inequalities for the first two connectivity objectives by examining intermediate dynamic programming solutions to k-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches.

Original languageEnglish (US)
Pages (from-to)172-188
Number of pages17
JournalDiscrete Optimization
Volume9
Issue number3
DOIs
StatePublished - Aug 1 2012
Externally publishedYes

Keywords

  • Mixed-integer programming
  • Network interdiction
  • Valid inequalities

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Exact interdiction models and algorithms for disconnecting networks via node deletions'. Together they form a unique fingerprint.

  • Cite this