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

DOI10.1007/978-3-642-16926-7_10MaRDI QIDQ3057615zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Solving Capacitated Dominating Set by using covering by subsets and maximum matching
• Capacitated Domination and Covering: A Parameterized Perspective
• On capacitated set cover problems
• Exact approaches for solving a covering problem with capacitated subtrees
• Capacitated domination: problem complexity and approximation algorithms
• Approximation algorithms for the capacitated domination problem
• Capacitated Domination Problem
• Capacitated domination problem
• An approach to the solution of the set-covering problem
• Exact and approximation algorithms for geometric and capacitated set cover problems

Cites work

• Capacitated domination faster than \(O(2^{n })\)
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph-Theoretic Concepts in Computer Science
• Inclusion/Exclusion Meets Measure and Conquer
• Partitioning into sets of bounded cardinality
• Planar capacitated dominating set is \(W[1]\)-hard
• Solving Connected Dominating Set Faster Than 2 n

Cited in

(7)

• Capacitated domination faster than \(O(2^{n })\)
• Solving Capacitated Dominating Set by using covering by subsets and maximum matching
• Capacitated domination faster than O(2ⁿ)
• Capacitated domination: problem complexity and approximation algorithms
• Maximum Covering Formulation for Open Locating Dominating Sets
• Moderately exponential time and fixed parameter approximation algorithms
• Exact approaches for solving a covering problem with capacitated subtrees

This page was built for publication: Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057615)