Restricted power domination and zero forcing problems

Chassidy Bozeman (), Boris Brimkov (), Craig Erickson (), Daniela Ferrero (), Mary Flagg () and Leslie Hogben ()
Additional contact information
Chassidy Bozeman: Iowa State University
Boris Brimkov: Rice University
Daniela Ferrero: Texas State University
Mary Flagg: University of St. Thomas
Leslie Hogben: Iowa State University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 3, No 9, 935-956

Abstract: 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.

Keywords: Power domination; Restricted power domination; Zero forcing; Restricted zero forcing; 05C69; 05C50; 05C57; 94C15 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0330-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:3:d:10.1007_s10878-018-0330-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0330-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().