Parameterized power domination complexity

DOI10.1016/J.IPL.2006.01.007MaRDI QIDQ844180zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Improved algorithms and complexity results for power domination in graphs
• Fundamentals of Computation Theory
• Domination in Graphs Applied to Electric Power Networks
• The k-power domination problem in weighted trees
• The \(k\)-power domination problem in weighted trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1262783 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Complexity Results for Bandwidth Minimization
• Domination in Graphs Applied to Electric Power Networks
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Graph minors. I. Excluding a forest
• On the structure of parameterized problems in NP
• Parameterized and Exact Computation

Cited in

(25)

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

This page was built for publication: Parameterized power domination complexity

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