Parameterized power domination complexity

DOI10.1016/j.ipl.2006.01.007zbMath1187.68249OpenAlexW2039168577MaRDI QIDQ844180

Stefan Richter, Peter Rossmanith, Daniel Mölle, Joachim Kneis

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.01.007

zbMATH Keywords

computational complexitygraph algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

Hybrid search for the optimal PMU placement problem on a power grid ⋮ Hardness results of connected power domination for bipartite graphs and chordal graphs ⋮ Power domination in Mycielskian of spiders ⋮ Power domination in circular-arc graphs ⋮ Connected power domination in graphs ⋮ An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Generalized power domination of graphs ⋮ Power domination in honeycomb networks ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Generalized power domination: propagation radius and Sierpiński graphs ⋮ Restricted power domination and fault-tolerant power domination on grids ⋮ Editorial: Tails and ties ⋮ Failed power domination on graphs ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ On the power domination number of the generalized Petersen graphs ⋮ Power domination with bounded time constraints ⋮ \(k\)-power domination in block graphs ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Power domination in cylinders, tori, and generalized Petersen graphs ⋮ Power domination throttling ⋮ Minimum Power Dominating Sets of Random Cubic Graphs ⋮ Generalized power domination in claw-free regular graphs

Cites Work

• Graph minors. I. Excluding a forest
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• On the structure of parameterized problems in NP
• Complexity Results for Bandwidth Minimization
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Domination in Graphs Applied to Electric Power Networks
• Parameterized and Exact Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parameterized power domination complexity