Computing Hitting Set Kernels By AC^0-Circuits

DOI10.4230/LIPIcs.STACS.2018.9zbMath1487.68133arXiv1801.00716OpenAlexW2963821498MaRDI QIDQ3304103

Till Tantau, Max Bannach

Publication date: 5 August 2020

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

zbMATH Keywords

parallel computationfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Hypergraphs (05C65) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Networks and circuits as models of computation; circuit complexity (68Q06) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Unnamed Item ⋮ On the Descriptive Complexity of Color Coding

Cites Work

• Towards optimal and expressive kernelization for \(d\)-hitting set
• Advice classes of parametrized tractability
• An efficient fixed-parameter algorithm for 3-hitting set
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parametrized complexity theory.
• Scalable parallel algorithms for FPT problems
• Intersection Theorems for Systems of Sets
• Color-coding
• Some Lower Bounds in Parameterized AC^0.
• Parallel Multivariate Meta-Theorems
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing Hitting Set Kernels By AC^0-Circuits