Graduation Year
2010
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Susan Martonosi
Reader 2
Nicholas Pippenger
Terms of Use & License Information
Rights Information
© 2010 Yaniv J. Ovadia
Abstract
Disrupting terrorist and other covert networks requires identifying and capturing key leaders. Previous research by Martonosi et al. (2009) defines a load metric on vertices of a covert network representing the amount of communication in which a vertex is expected to participate. They suggest that the visibility of a target vertex can be increased by removing other, more accessible members of the network. This report evaluates the feasibility of efficiently calculating the optimal subset of vertices to remove. We begin by proving that the general problem of identifying the optimally load maximizing vertex set removal is NP-complete. We then consider the feasibility of more quickly computing the load maximizing single vertex removal by designing an efficient algorithm for recomputing Gomory- Hu trees. This leads to a result regarding the uniqueness of Gomory- Hu trees with implications towards the feasibility of one approach for Gomory- Hu tree reconstruction. Finally, we propose a warm start algorithm which performs this reconstruction, and analyze its runtime experimentally.
Recommended Citation
Ovadia, Yaniv J., "Computational Feasibility of Increasing the Visibility of Vertices in Covert Networks" (2010). HMC Senior Theses. 15.
https://scholarship.claremont.edu/hmc_theses/15
Comments
Previously linked to as: http://ccdl.libraries.claremont.edu/u?/stc,329