Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching

DOI10.1007/978-3-642-16926-7_10zbMath1310.05162OpenAlexW1690875420MaRDI QIDQ3057615

Mathieu Liedloff, Ioan Todinca, Yngve Villanger

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Capacitated Domination Faster Than O(2 n )
• Inclusion/Exclusion Meets Measure and Conquer
• Planar Capacitated Dominating Set Is W[1-Hard]
• Partitioning into Sets of Bounded Cardinality
• Solving Connected Dominating Set Faster Than 2 n
• Graph-Theoretic Concepts in Computer Science