Fort Neighborhoods: A Set Cover Formulation for Power Domination

[摘要] This thesis introduces a novel separation algorithm for calculating power dominationnumbers and minimum power dominating sets in graphs. Additionally, it shows how theexistence of solutions of special forms can be exploited by computational methods. Powerdomination studies arise from a key problem in electrical engineering concerning placementsof monitoring devices known as Phasor Measurement Units (PMUs). PMUs areinstalled in electrical networks for early detection of electrical imbalances, enabling correctiveactions to mitigate outages. In graph representations of electrical networks, powerdominating 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 powerdominating sets and their cardinality, known is the graph’s power domination number. Unlikeprior methods, this work exploits crucial yet previously neglected graph structures: theneighborhoods of zero forcing forts. Utilizing these structures, algorithms are devised forcalculating minimum power dominating sets and the power domination numbers of graphs.Computational experiments demonstrating an order of magnitude improvement over previousmethods are presented.

[发布机构] Rice University

[效力级别] Optimization