An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}

DOI10.1007/s00453-011-9533-2zbMath1236.68077OpenAlexW1977068662MaRDI QIDQ2429350

Henning Fernau, Daniel Binkele-Raible

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9533-2

zbMATH Keywords

measure and conquermoderately exponential time algorithmsdomination-type problemsNP-hardness results

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Hybrid search for the optimal PMU placement problem on a power grid ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Power domination with bounded time constraints ⋮ Algorithms and Complexity of Power Domination in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Refined memorization for vertex cover
• Parameterized power domination complexity
• Solving connected dominating set faster than \(2^n\)
• Improved algorithms and complexity results for power domination in graphs
• Power domination in block graphs
• An Amortized Search Tree Analysis for k-Leaf Spanning Tree
• A measure & conquer approach for the analysis of exact algorithms
• Power Domination in $\mathcal{O}^*(1.7548^n)$ Using Reference Search Trees
• Inclusion/Exclusion Meets Measure and Conquer
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• Algorithms for maximum independent sets
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Domination in Graphs Applied to Electric Power Networks
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• The PMU Placement Problem
• Computing and Combinatorics
• Approximation Algorithms and Hardness for Domination with Propagation

This page was built for publication: An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}