# 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

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.