Approximation Algorithms and Hardness for Domination with Propagation

DOI10.1007/978-3-540-74208-1_1zbMath1171.68867OpenAlexW1520529901MaRDI QIDQ5901420

Ashkan Aazami, Michael D. Stilp

Publication date: 17 February 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74208-1_1

zbMATH Keywords

integer programmingplanar graphsdominating setapproximation algorithmsgreedy algorithmshardness of approximationPTASpower dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) 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) Approximation algorithms (68W25)

Related Items

Observing the State of a Smart Grid Using Bilevel Programming ⋮ Improved approximation algorithms for label cover problems ⋮ Complexity and inapproximability results for the power edge set problem ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Restricted power domination and fault-tolerant power domination on grids ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Vertex sequences in graphs

This page was built for publication: Approximation Algorithms and Hardness for Domination with Propagation