Node Deletion and Edge Deletion Problems in Networks
Abstract
This project plans to develop efficient algorithms to study the node and edge deletion problems on networks. These problems stem from various important applications in energy networks (e.g., how to build a network that can survive failures on particular power lines), epidemic containment (e.g., how to ensure disconnectivity between various populations) and defense operations (e.g., where to focus attacks on enemy to ensure faster victory). The problem involves in effectively identifying a subset of nodes or edges of a network, which on deletion results in a subgraph with desirable properties. Some of the properties of interest include the connectivity in the graph, a restrictive size of the largest component, and denseness of the components formed. The property under study, however, must satisfy two conditions, namely, hereditary and non-triviality [4]. The properties pro-posed help in designing attack and defense strategies for networks in order to study and/orexploit vulnerabilities in a network.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2017
- Source ID
- FA95501710029
Entities
People
- VinÃcius L. de Lima
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Strathclyde