Algorithms and complexity of power domination in graphs

DOI10.1007/978-3-030-58892-2_15MaRDI QIDQ3384121zbMATH OpenOpenAlexFDO

Authors Stephen T. Hedetniemi, Alice A. McRae, Raghuveer Mohan

Publication date 14 December 2021

Published in Developments in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-58892-2_15

zbMATH Keywords

complexity of computingpower domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Power domination throttling
• Domination in Graphs Applied to Electric Power Networks
• Improved algorithms and complexity results for power domination in graphs
• Fundamentals of Computation Theory
• Computing and Combinatorics

Cites work

• \(k\)-power domination in block graphs
• A linear algorithm for the domination number of a tree
• A note on power domination in grid graphs
• A threshold of ln n for approximating set cover
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• Approximation Algorithms and Hardness for Domination with Propagation
• Approximation Algorithms and Hardness for Domination with Propagation
• Computing and Combinatorics
• Connected power domination in graphs
• Domination in Graphs Applied to Electric Power Networks
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• Fundamentals of Computation Theory
• Generalized power domination in regular graphs
• Generalized power domination of graphs
• scientific article; zbMATH DE number 5138348 (Why is no real title available?)
• scientific article; zbMATH DE number 714489 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Improved algorithms and complexity results for power domination in graphs
• Linear algorithms on recursive representations of trees
• Minimum power dominating sets of random cubic graphs
• Minimum rank of skew-symmetric matrices described by a graph
• On the \({k}\)-power domination of hypergraphs
• Parameterized power domination complexity
• Power Domination in $\mathcal{O}^*(1.7548^n)$ Using Reference Search Trees
• Power domination in block graphs
• Power domination in certain chemical structures
• Power domination in circular-arc graphs
• Power domination in cylinders, tori, and generalized Petersen graphs
• Power domination in graphs
• Power domination in graphs
• Power domination in honeycomb networks
• Power Domination in Product Graphs
• Power domination with bounded time constraints
• Restricted power domination and fault-tolerant power domination on grids
• Restricted power domination and zero forcing problems
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The PMU Placement Problem
• Zero forcing and power domination for graph products
• Zero forcing sets and the minimum rank of graphs

Cited in

(10)

• On the power domination number of de Bruijn and Kautz digraphs
• Power domination in circular-arc graphs
• Power domination throttling
• Algorithms for hierarchical power
• On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• Fundamentals of Computation Theory
• Generalized Powers of Graphs and Their Algorithmic Use
• Hardness Results and Efficient Algorithms for Graph Powers
• Some product graphs with power dominating number at most 2

This page was built for publication: Algorithms and complexity of power domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3384121)