Fort Neighborhoods: A Set Cover Formulation for Power Domination

This thesis introduces a novel separation algorithm for calculating power domination numbers and minimum power dominating sets in graphs. Additionally, it shows how the existence of solutions of special forms can be exploited by computational methods. Power domination studies arise from a key problem in electrical engineering concerning placements of monitoring devices known as Phasor Measurement Units (PMUs). PMUs are installed in electrical networks for early detection of electrical imbalances, enabling corrective actions to mitigate outages. In graph representations of electrical networks, power dominating sets denote locations at which PMUs can be placed to monitor entire networks. Due to PMU installation costs of up to $200,000, it is desirable to identify minimum power dominating sets and their cardinality, known is the graph’s power domination number. Unlike prior methods, this work exploits crucial yet previously neglected graph structures: the neighborhoods of zero forcing forts. Utilizing these structures, algorithms are devised for calculating minimum power dominating sets and the power domination numbers of graphs. Computational experiments demonstrating an order of magnitude improvement over previous methods are presented