Pseudo-Separation for Assessment of Structural Vulnerability of a Network
Abstract
Based upon the idea that network functionality is impaired if two nodes in a network are sufficiently separated in terms of a given metric, we introduce two combinatorial pseudocut problems generalizing the classical min-cut and multi-cut problems. We expect the pseudocut problems will find broad relevance to the study of network reliability. We comprehensively analyze the computational complexity of the pseudocut problems and provide three approximation algorithms for these problems. Motivated by applications in communication networks with strict Quality-of-Service (QoS) requirements, we demonstrate the utility of the pseudocut problems by proposing a targeted vulnerability assessment for the structure of communication networks using QoS metrics; we perform experimental evaluations of our proposed approximation algorithms in this context.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 05, 2017
- Source ID
- 10.1145/3143314.3078538
Entities
People
- Alan Kuhnle
- Md Abdul Alim
- My T Thai
- Tianyi Pan
- Victoria G. Crawford
Organizations
- Defense Threat Reduction Agency
- National Science Foundation
- University of Florida