Improved algorithms and complexity results for power domination in graphs
type: Item
instance of: scholarly article
title: Improved algorithms and complexity results for power domination in graphs
zbMATH Open document ID: 1170.68031
author: Jiong Guo
author: Rolf Niedermeier
author: Daniel Raible
published in: Algorithmica
publication date: 2008-12-02T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5377141
zbMATH Keywords: design and analysis of algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: parameterized complexity
zbMATH Keywords: fixed-parameter algorithms
zbMATH Keywords: graph algorithms
zbMATH Keywords: graphs of bounded treewidth
zbMATH Keywords: power domination in graphs
MaRDI profile type: Publication
full work available at URL: s00453-007-9147-x
OpenAlex ID: W2045704027
cites work: Approximation Algorithms and Hardness for Domination with Propagation
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: A refined search tree technique for dominating set on planar graphs
cites work: Polynomial-time data reduction for dominating set
cites work: Q3044360
cites work: Q4258216
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Treewidth: Characterizations, Applications, and Computations
cites work: Dominating Sets in Chordal Graphs
cites work: Graph Classes: A Survey
cites work: The PMU Placement Problem
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: A note on power domination in grid graphs
cites work: A threshold of ln n for approximating set cover
cites work: Q4198056
cites work: Parameterized and Exact Computation
cites work: Domination in Graphs Applied to Electric Power Networks
cites work: Q4368729
cites work: Q4368728
cites work: An optimal algorithm for finding dominating cycles in circular-arc graphs
cites work: Treewidth. Computations and approximations
cites work: Parameterized power domination complexity
cites work: Q4378629
cites work: Computing and Combinatorics
cites work: Q5710169
cites work: Q4407447
cites work: Algorithms for Vertex Partitioning Problems on Partial k-Trees
cites work: Q4782696
DOI: 10.1007/S00453-007-9147-X
description: scientific article; zbMATH DE number 5377141