• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Computational Feasibility of Increasing the Visibility of Vertices in Covert Networks

Ovadia, Yaniv J. 30 May 2010 (has links)
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.

Page generated in 0.046 seconds