Improved algorithms and complexity results for power domination in graphs

DOI10.1007/s00453-007-9147-xzbMath1170.68031OpenAlexW2045704027MaRDI QIDQ958210

Rolf Niedermeier, Daniel Raible, Jiong Guo

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9147-x

zbMATH Keywords

computational complexitygraph algorithmsfixed-parameter algorithmsparameterized complexitygraphs of bounded treewidthdesign and analysis of algorithmspower domination in graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

Nordhaus-Gaddum problems for power domination ⋮ The k-power bondage number of a graph ⋮ Hybrid search for the optimal PMU placement problem on a power grid ⋮ Hardness results of connected power domination for bipartite graphs and chordal graphs ⋮ Note on power propagation time and lower bounds for the power domination number ⋮ On the \({k}\)-power domination of hypergraphs ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ Restricted power domination and zero forcing problems ⋮ Power domination in circular-arc graphs ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Generalized power domination of graphs ⋮ Complexity and lowers bounds for power edge set problem ⋮ Generalized power domination: propagation radius and Sierpiński graphs ⋮ Restricted power domination and fault-tolerant power domination on grids ⋮ On the Power Domination Number of Graph Products ⋮ Power domination with bounded time constraints ⋮ \(k\)-power domination in block graphs ⋮ The \(k\)-power domination problem in weighted trees ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Disproofs of three conjectures on the power domination of graphs ⋮ Power domination in regular claw-free graphs ⋮ Power domination on triangular grids with triangular and hexagonal shape ⋮ Power domination throttling ⋮ Minimum Power Dominating Sets of Random Cubic Graphs ⋮ Generalized power domination in claw-free regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized power domination complexity
• An optimal algorithm for finding dominating cycles in circular-arc graphs
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• A note on power domination in grid graphs
• A refined search tree technique for dominating set on planar graphs
• A threshold of ln n for approximating set cover
• Treewidth: Characterizations, Applications, and Computations
• Polynomial-time data reduction for dominating set
• Dominating Sets in Chordal Graphs
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Domination in Graphs Applied to Electric Power Networks
• Parameterized and Exact Computation
• The PMU Placement Problem
• Computing and Combinatorics
• Approximation Algorithms and Hardness for Domination with Propagation

This page was built for publication: Improved algorithms and complexity results for power domination in graphs