Computing small partial coverings
From MaRDI portal
Publication:1007552
DOI10.1016/S0020-0190(02)00434-9zbMATH Open1173.68854OpenAlexW2073689249MaRDI QIDQ1007552FDOQ1007552
Authors: Markus Bläser 
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00434-9
Recommendations
- Approximation algorithms for partial covering problems
- scientific article; zbMATH DE number 1754596
- Implicit branching and parameterized partial cover problems (extended abstract)
- An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
- Using homogeneous weights for approximating the partial cover problem
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- Color-coding
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved performance of the greedy algorithm for partial cover
- Vertex cover: Further observations and further improvements
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (30)
- A parameterized approximation scheme for generalized partial vertex cover
- Parameterized complexity of the anchored \(k\)-core problem for directed graphs
- On the parameterized complexity of separating certain sources from the target
- Improved Upper Bounds for Partial Vertex Cover
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- Partial vertex cover and budgeted maximum coverage in bipartite graphs
- On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
- Parameterized dynamic variants of red-blue dominating set
- Implicit branching and parameterized partial cover problems
- Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
- On algorithms for construction of all irreducible partial covers
- Restricted parameter range promise set cover problems are easy
- FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
- Hitting and covering partially
- Capacitated Domination and Covering: A Parameterized Perspective
- Using homogeneous weights for approximating the partial cover problem
- Subexponential algorithms for partial cover problems
- String editing under pattern constraints
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- Implicit branching and parameterized partial cover problems (extended abstract)
- On the positive-negative partial set cover problem
- Moderately exponential time and fixed parameter approximation algorithms
- Combinatorial search in two and more rounds
- Max-SAT with cardinality constraint parameterized by the number of clauses
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Representative families: a unified tradeoff-based approach
- Approximation algorithms for partial covering problems
- Partially polynomial kernels for set cover and test cover
This page was built for publication: Computing small partial coverings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007552)
