Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 28, Issue 1, Pages 3-24Publisher
SPRINGER
DOI: 10.1007/s10878-014-9742-0
Keywords
Vulnerability assessment; Pairwise connectivity; Integer programming; Spectral bound
Funding
- NSF CAREER Award [0953284]
- Direct For Computer & Info Scie & Enginr
- Division Of Computer and Network Systems [0953284] Funding Source: National Science Foundation
Ask authors/readers for more resources
Assessing network systems for failures is critical to mitigate the risk and develop proactive responses. In this paper, we investigate devastating consequences of link failures in networks. We propose an exact algorithm and a spectral lower-bound on the minimum number of removed links to incur a significant level of disruption. Our exact solution can identify optimal solutions in both uniform and weighted networks through solving a well-constructed mixed integer program. Also, our spectral lower-bound derives from the Laplacian eigenvalues an estimation on the vulnerability of large networks that are intractable for exact methods. Through experiments on both synthetic and real-world networks, we demonstrate the efficiency of the proposed methods.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available