Capacitated Domination Faster Than O(2 n )
From MaRDI portal
Publication:3569880
DOI10.1007/978-3-642-13731-0_8zbMath1285.68063OpenAlexW2069569782MaRDI QIDQ3569880
Marek Cygan, Jakub Onufry Wojtaszczyk, Marcin Pilipczuk
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (8)
Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ When polynomial approximation meets exact computation ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ When polynomial approximation meets exact computation ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Capacitated domination: problem complexity and approximation algorithms
This page was built for publication: Capacitated Domination Faster Than O(2 n )
