Capacitated Domination Faster Than O(2 n )

DOI10.1007/978-3-642-13731-0_8zbMATH Open1285.68063OpenAlexW2069569782MaRDI QIDQ3569880FDOQ3569880

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

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)

Cited In (8)

• Solving Capacitated Dominating Set by using covering by subsets and maximum matching
• Capacitated domination: problem complexity and approximation algorithms
• Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
• Solving Target Set Selection with Bounded Thresholds Faster than 2^n
• When polynomial approximation meets exact computation
• When polynomial approximation meets exact computation
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation

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)