Capacitated domination faster than \(O(2^n)\)
From MaRDI portal
Publication:1944213
DOI10.1016/j.ipl.2011.09.004zbMath1260.68494OpenAlexW2069751859MaRDI QIDQ1944213
Marek Cygan, Jakub Onufry Wojtaszczyk, Marcin Pilipczuk
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.09.004
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Time-approximation trade-offs for inapproximable problems ⋮ Enumeration of minimal tropical connected sets ⋮ Exact capacitated domination: on the computational complexity of uniqueness ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Uniqueness of \(DP\)-Nash subgraphs and \(D\)-sets in weighted graphs of Netflix games
Cites Work
- Unnamed Item
- Unnamed Item
- Exact exponential algorithms.
- Exponential-time approximation of weighted set cover
- Efficiency in exponential time for domination-type problems
- Approximating the bandwidth of caterpillars
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- A measure & conquer approach for the analysis of exact algorithms
- Capacitated Domination and Covering: A Parameterized Perspective
- Fourier meets M\"{o}bius: fast subset convolution
- Exact and Approximate Bandwidth
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Inclusion/Exclusion Meets Measure and Conquer
- Planar Capacitated Dominating Set Is W[1-Hard]
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Faster Exact Bandwidth
- Counting Subgraphs via Homomorphisms
This page was built for publication: Capacitated domination faster than \(O(2^n)\)
