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.
| Identifer | oai:union.ndltd.org:wm.edu/oai:scholarworks.wm.edu:etd-6854 |
| Date | 01 January 2019 |
| Creators | Sweigart, Daniel Blair |
| Publisher | W&M ScholarWorks |
| Source Sets | William and Mary |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations, Theses, and Masters Projects |
| Rights | © The Author |
Page generated in 0.0523 seconds