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
integer programmingplanar graphsdominating setapproximation algorithmsgreedy algorithmshardness of approximationPTASpower dominating set
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
This page was built for publication: Approximation Algorithms and Hardness for Domination with Propagation