An integer programming framework for critical elements detection in graphs

Alexander Veremyev, Oleg A. Prokopyev () and Eduardo L. Pasiliao
Additional contact information
Alexander Veremyev: Air Force Research Laboratory, Munitions Directorate
Oleg A. Prokopyev: University of Pittsburgh
Eduardo L. Pasiliao: Air Force Research Laboratory, Munitions Directorate

Journal of Combinatorial Optimization, 2014, vol. 28, issue 1, No 13, 233-273

Abstract: Abstract This study presents an integer programming framework for minimizing the connectivity and cohesiveness properties of a given graph by removing nodes and edges subject to a joint budgetary constraint. The connectivity and cohesiveness metrics are assumed to be general functions of sizes of the remaining connected components and node degrees, respectively. We demonstrate that our approach encompasses, as special cases (possibly, under some mild conditions), several other models existing in the literature, including minimization of the total number of connected node pairs, minimization of the largest connected component size, and maximization of the number of connected components. We discuss computational complexity issues, derive linear mixed integer programming (MIP) formulations, and describe additional modeling enhancements aimed at improving the performance of MIP solvers. We also conduct extensive computational experiments with real-life and randomly generated network instances under various settings that reveal interesting insights and demonstrate advantages and limitations of the proposed framework.

Keywords: Critical node detection; Critical edge detection; Network interdiction; Mixed integer programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9730-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:28:y:2014:i:1:d:10.1007_s10878-014-9730-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9730-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().