Considering the isolation set problem

• Published in: European journal of operational research 2013-06, Vol.227 (2), p.268-274
• Main Authors: Herbranson, Travis J., Deckro, Richard F., Chrissis, James W., Hamill, Jonathan (Todd)
• Format: Article
• Language: English
• Subjects: Integer Program; Isolation Set Problem; Network Centric Warfare; Network flow problem; Network security; Networks; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2012.11.016

► The Isolation Set Problem is reviewed and characteristics of the problem are addressed. ► Several approaches, including node consolidation, node inclusion, and adding resource constraints are presented. ► Approach can aid in identifying critical connections and member of a network. Given a network, G=[N,E] the Isolation Set Problem (ISP) finds the set of arcs, D⊆E, that when removed will separate a predefined set of r distinguished nodes [2]. This involves eliminating connections from a specific set of nodes to the rest of a network. In our increasingly interconnected network-centric world, this might be isolating various units from Headquarters; isolating a portion of a computer network to disrupt communications or to quarantine a virus or some other form of cyber attack; or isolating a cell or sub-group in a terrorist or “dark” network, for example. The research presented here reviews the ISP, addresses the totally unimodular character of the ISP, offers a node consolidation method, provides for the inclusion of nodes in the cut sets, and introduces resource constraints to the ISP. An example is presented to illustrate the approach.