Power Domination
Collaborator
Dr. Beth Morrison-Bjorkman
54th SEICCGTC (Boca)
At the 54th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, I presented work on the creation of the Power Domination Toolbox. This toolbox allows deeper inspection of larger network structure.
Abstract
Phasor Measurement Units (PMUs) are used to monitor the power grid. Efficient placement of PMUs is modeled by the power domination process. The creation of the Power Domination Toolbox will allow academics and researchers the ability to investigate power domination on graphs they were previously unable to investigate due to a prohibitively long runtime. Wavefront zero forcing, graph theoretical concepts, and parallel computing methodologies are combined into one cohesive toolbox. This toolbox makes small networks feasible on average computers and can analyze much larger networks on High Performance Computers (HPCs).
Power_Domination_Toolbox.pdfPower Domination
The power domination algorithm [1] is:
(Domination step) Color each node adjacent to the seed set
(Zero forcing step) While there exists a colored nmode that is adjacent to exactly one uncolored node, color the uncolored node.
A power dominating set is any set of vertices that result in the entire graph being colored.
Current State-of-the-Art
Brute force algorithm checks every subset of the entire vertex set
SageMath notebooks running on remote servers
SageMath hooks into wavefront zero forcing [2]
Methods Used
Shrinking the graph (red)
Locating preferred vertices guaranteed to be in some minimum power dominating set (yellow)
Parallel computing techniques
Efficient parallelization
Algorithm Flow
Results
Jupyter notebook for local computers
Python script for remote servers (HPCs)
Unit tests in the Jupyter notebook
Power grids like New England [3] that took half a mionute to find a power dominating set now take under half a second
Original Algorithm (Red)
Power Domination Toolbox (Blue)
Future Work
Distribution of labor across HPC nodes
Robust power domination
Leveraging NP-Completeness
Probabilistic power domination
References
T.W. Haynes, S. T. Hedetniemi, and M. A. Henning, "Domination in graphs applied to electric power networks," SIAM Journal in Discrete Mathematics, vol. 15, pp. 519-529, jan 2002.
J. Group, "Minimum rank sage library," 2019.
R. D. Zimmerman, C. E. Murillo-Sanchez, and R. J. Thomas, "MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education," IEEE Transactions on Power Systems, vol. 26, pp. 12-19, feb 2011.