Solving Capacitated Dominating Set by using covering by subsets and maximum matching

DOI10.1016/j.dam.2012.10.021zbMath1285.05142MaRDI QIDQ2442208

Mathieu Liedloff, Ioan Todinca, Yngve Villanger

Publication date: 2 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hard problemexact exponential-time algorithmscapacitated dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Iterative partial rounding for vertex cover with hard capacities

Cites Work

• Unnamed Item
• Solving connected dominating set faster than \(2^n\)
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Capacitated Domination and Covering: A Parameterized Perspective
• Capacitated Domination Faster Than O(2 n )
• 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

This page was built for publication: Solving Capacitated Dominating Set by using covering by subsets and maximum matching