Fort Neighborhoods: A Set Cover Formulation for Power Domination

Date
2018-11-14
Journal Title
Journal ISSN
Volume Title
Publisher
Description
Abstract

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.

Description
Degree
Master of Arts
Type
Thesis
Keywords
Combinatorial Optimization, Graph Theory, Discrete Mathematics
Citation

Smith, Logan. "Fort Neighborhoods: A Set Cover Formulation for Power Domination." (2018) Master’s Thesis, Rice University. https://hdl.handle.net/1911/105803.

Has part(s)
Forms part of
Published Version
Rights
Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.
Link to license
Citable link to this page