Capacitated domination faster than O(2ⁿ )

DOI10.1007/978-3-642-13731-0_8MaRDI QIDQ3569880zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk

Publication date 22 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13731-0_8

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Capacitated domination faster than \(O(2^n)\)
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Solving Capacitated Dominating Set by using covering by subsets and maximum matching
• Approximation algorithms for the capacitated domination problem
• Capacitated domination.

Cited in

(12)

• Capacitated domination faster than \(O(2^n)\)
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• When polynomial approximation meets exact computation
• Solving Capacitated Dominating Set by using covering by subsets and maximum matching
• Capacitated Domination and Covering: A Parameterized Perspective
• Capacitated domination.
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Capacitated domination: problem complexity and approximation algorithms
• When polynomial approximation meets exact computation
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Exact capacitated domination: on the computational complexity of uniqueness

This page was built for publication: Capacitated domination faster than \(O(2^{n })\)

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