A&S Graduate Studies
[PAST EVENT] Robin Givens, Computer Science - Oral Exam for the Ph.D. Degree
Abstract:
The detection and location of issues in a network is a common problem encompassing a wide variety of research areas. Location detection problems have been studied for wireless sensor networks (WSNs) and environmental monitoring, microprocessor fault detection, public utility contamination, and finding intruders in buildings. Modeling these systems as a graph, we want to find the smallest subset of vertices that, when sensors are placed at those locations, can detect and locate any anomalies that emerge. One kind of set that solves this problem is the open locating-dominating set (OLD-set), a set of vertices that forms a unique and nonempty neighborhood with every vertex in the graph.
For this work, we begin with a study of OLD-sets in circulant graphs. Circulant graphs are a group of regular cyclic graphs that are often used in massively parallel systems. We prove the optimal OLD-set size for two circulant graphs using two proof techniques: the discharging method and Hall's Theorem.
Next we introduce the mixed-weight open locating-dominating set (mixed-weight OLD-set), an extension of the OLD-set. The mixed-weight OLD-set allows vertices in the graph to have different weights, representing systems that use sensors of varying strengths. This is a novel approach to the study of location detection problems. We show that the decision problem for the minimum mixed-weight OLD-set, for any weights up to positive integer d, is NP-complete. We consider mixed-weight OLD-sets in random graphs by providing probabilistic bounds on the size of the mixed-weight OLD-set and use simulation to reinforce the theoretical results.
Finally, we present our research plan to study mixed-weight OLD-sets in paths and cycles, estimate bounds on the size of the sets in geometric random graphs, and provide an integer linear program to solve for mixed-weight OLD-sets.
Biography:
Robin Givens is a Ph.D. candidate at William & Mary in the Department of Computer Science. She is advised by Dr. Weizhen Mao (chair), Dr. Gexin Yu, and Dr. Rex Kincaid. Her research interests include graph theory and optimization. Robin received a B.S. in mathematics and computer science at the University of Richmond in 2006 and an M.S. in computer science at William & Mary in 2014. Robin began a tenure-track position in the Computer Science Department at Randolph-Macon College in the fall of 2016.