Graduation Year


Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science



Reader 1

Susan Martonosi

Reader 2

Nicholas Pippenger

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2010 Yaniv J. Ovadia


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.


Previously linked to as:,329

Included in

Mathematics Commons