An efficient algorithm for power dominating set

DOI10.1007/S00453-024-01283-8MaRDI QIDQ7022272zbMATH OpenFDO

Authors Thomas Bläsius, Max Göttlicher

Publication date 25 February 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-024-01283-8

zbMATH Keywords

implicit hitting setparameterized complexitypower dominating setreduction rules

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A technique for computing the zero forcing number of a graph with a cut-vertex
• An efficient algorithm for power dominating set
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• Computational approaches for zero forcing and related problems
• 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 parameterized complexity
• Improved algorithms and complexity results for power domination in graphs
• LMHS: a SAT-IP hybrid MaxSat solver
• On the structure of parameterized problems in NP
• Parameterized power domination complexity
• Power domination in block graphs
• Power domination in circular-arc graphs
• Restricted power domination and zero forcing problems
• The PMU Placement Problem

Cited in

(1)

• Multiparent path relinking. An application to the power dominating set problem

This page was built for publication: An efficient algorithm for power dominating set

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