Skip to main content
Article
Restricted power domination and zero forcing problems
Journal of Combinatorial Optimization
  • Chassidy Bozeman, Iowa State University
  • Boris Brimkov, Rice University
  • Craig Erickson, Saint Paul, USA
  • Daniela Ferrero, Texas State University - San Marcos
  • Mary Flagg, University of St. Thomas
  • Leslie Hogben, Iowa State University and American Institute of Mathematics
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
4-1-2019
DOI
10.1007/s10878-018-0330-6
Abstract

Power domination in graphs arises from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A power dominating set of a graph is a set of vertices that observes every vertex in the graph, following a set of rules for power system monitoring. A practical problem of interest is to determine the minimum number of additional measurement devices needed to monitor a power network when the network is expanded and the existing devices remain in place. In this paper, we study the problem of finding the smallest power dominating set that contains a given set of vertices X. We also study the related problem of finding the smallest zero forcing set that contains a given set of vertices X. The sizes of such sets in a graph G are respectively called the restricted power domination number and restricted zero forcing number of G subject to X. We derive several tight bounds on the restricted power domination and zero forcing numbers of graphs, and relate them to other graph parameters. We also present exact and algorithmic results for computing the restricted power domination number, including integer programs for general graphs and a linear time algorithm for graphs with bounded treewidth. We also use restricted power domination to obtain a parallel algorithm for finding minimum power dominating sets in trees.

Comments

This is a post-peer-review, pre-copyedit version of an article published in Journal of Combinatorial Optimization. The final authenticated version is available online at DOI: 10.1007/s10878-018-0330-6. Posted with permission.

Copyright Owner
Springer Science+Business Media, LLC
Language
en
File Format
application/pdf
Citation Information
Chassidy Bozeman, Boris Brimkov, Craig Erickson, Daniela Ferrero, et al.. "Restricted power domination and zero forcing problems" Journal of Combinatorial Optimization Vol. 37 Iss. 3 (2019) p. 935 - 956
Available at: http://works.bepress.com/leslie-hogben/88/