Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

DOI10.1007/978-3-319-18173-8_18zbMath1459.68086OpenAlexW599066741MaRDI QIDQ2947024

Neeldhara Misra, Vikram Kamat

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18173-8_18

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient fixed-parameter algorithm for 3-hitting set
• Parametrized complexity theory.
• The Approximability of Constraint Satisfaction Problems
• Preprocessing of Min Ones Problems: A Dichotomy
• Kernelization: New Upper and Lower Bound Techniques
• Improved Fixed-Parameter Algorithm for the Minimum Weight 3-SAT Problem
• Parameterized and Exact Computation
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

This page was built for publication: Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints