Parameterized algorithms and kernels for 3-hitting set with parity constraints

DOI10.1007/978-3-319-18173-8_18MaRDI QIDQ2947024zbMATH OpenOpenAlexFDO

Authors Vikram Kamat, Neeldhara Misra

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

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

Recommendations

• An efficient fixed-parameter algorithm for 3-hitting set
• Parameterized complexity of d-hitting set with quotas
• Parameterized approximation algorithms for hitting set
• Linear kernelizations for restricted 3-Hitting Set problems
• Parameterized algorithmics for d-HITTING SET

Cites work

• An efficient fixed-parameter algorithm for 3-hitting set
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
• Kernelization: new upper and lower bound techniques
• Parameterized and Exact Computation
• Parametrized complexity theory.
• Preprocessing of min ones problems: a dichotomy
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The approximability of constraint satisfaction problems

Cited in

(2)

• Fixed-parameter algorithms for fair hitting set problems
• Faster parameterized algorithms for variants of \textsc{3-hitting set}

This page was built for publication: Parameterized algorithms and kernels for 3-hitting set with parity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947024)