Exact interdiction models and algorithms for disconnecting networks via node deletions

Exact interdiction models and algorithms for disconnecting networks via node deletions

0.00 Avg rating0 Votes
Article ID: iaor20124610
Volume: 9
Issue: 3
Start Page Number: 172
End Page Number: 188
Publication Date: Aug 2012
Journal: Discrete Optimization
Authors: , ,
Keywords: combinatorial optimization, programming: multiple criteria, programming: integer, graphs
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 equ1‐hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches.

Reviews

Required fields are marked *. Your email address will not be published.