Linear kernelizations for restricted 3-Hitting Set problems

DOI10.1016/j.ipl.2009.03.004zbMath1209.68271MaRDI QIDQ989471

Xuan Cai

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.311.7613

zbMATH Keywords

computational complexity; kernelization; 3-Hitting Set problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of finding regular induced subgraphs
• Solving large FPT problems on coarse-grained parallel machines
• Parametrized complexity theory.
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• On Problems without Polynomial Kernels (Extended Abstract)
• Polynomial-time data reduction for dominating set
• Kernelization Algorithms for d-Hitting Set Problems
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Improved lower bounds on k‐independence
• Vertex packings: Structural properties and algorithms
• Nondeterminism within $P^ * $
• On the Fractional Covering Number of Hypergraphs
• Parameterized and Exact Computation
• Graph-Theoretic Concepts in Computer Science