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

power domination numbercomplexity of computing

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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 Product Graphs
• 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 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
• \(k\)-power domination in block graphs

Cited in

(10)

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

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)