Return to search

Optimization Approaches for Open-Locating Dominating Sets

An Open Locating-Dominating Set (OLD set) is a subset of vertices in a graph such that every vertex in the graph has a neighbor in the OLD set and every vertex has a unique set of neighbors in the OLD set. This can also represent where sensors, capable of detecting an event occurrence at an adjacent vertex, could be placed such that one could always identify the location of an event by the specific vertices that indicated an event occurred in their neighborhood. By the open neighborhood construct, which differentiates OLD sets from identifying codes, a vertex is not able to report if it is the location of the event. This construct provides a robustness over identifying codes and opens new applications such as disease carrier and dark actor identification in networks. This work explores various aspects of OLD sets, beginning with an Integer Linear Program for quickly identifying the optimal OLD set on a graph. As many graphs do not admit OLD sets, or there may be times when the total size of the set is limited by an external factor, a concept called maximum covering OLD sets is developed and explored. The coverage radius of the sensors is then expanded in a presentation of Mixed-Weight OLD sets where sensors can cover more than just adjacent vertices. Finally, an application is presented to optimally monitor criminal and terrorist networks using OLD sets and related concepts to identify the optimal set of surveillance targets.

Identiferoai:union.ndltd.org:wm.edu/oai:scholarworks.wm.edu:etd-6854
Date01 January 2019
CreatorsSweigart, Daniel Blair
PublisherW&M ScholarWorks
Source SetsWilliam and Mary
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceDissertations, Theses, and Masters Projects
Rights© The Author

Page generated in 0.0021 seconds