Parameterizations of test cover with bounded test sizes

DOI10.1007/s00453-014-9948-7zbMath1336.68120arXiv1209.6528OpenAlexW2095756139MaRDI QIDQ261370

F. Blanchet-Sadri, M. Dambrine

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.6528

zbMATH Keywords

fixed-parameter tractabilitypolynomial kerneltest covertests of bounded sizes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Deterministic versus randomized adaptive test cover ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Randomized Adaptive Test Cover ⋮ Combinatorial search in two and more rounds ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Partially Polynomial Kernels for Set Cover and Test Cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Approximation algorithms for the test cover problem
• A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
• (Non-)existence of polynomial kernels for the test cover problem
• Betweenness parameterized above tight lower bound
• Parametrized complexity theory.
• Induced subsets
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Max-Cut Parameterized above the Edwards-Erdős Bound
• Parameterized Study of the Test Cover Problem
• Partially Polynomial Kernels for Set Cover and Test Cover
• Incompressibility through Colors and IDs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Reducibility among Combinatorial Problems

This page was built for publication: Parameterizations of test cover with bounded test sizes