Dynamic kernels for hitting sets and set packing
type: Item
instance of: scholarly article
title: Dynamic kernels for hitting sets and set packing
author: Max Bannach
author: Zacharias Heinrich
author: Till Tantau
author: Rüdiger Reischuk
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608296
zbMATH Keywords: kernelization
zbMATH Keywords: dynamic algorithms
zbMATH Keywords: hitting set
zbMATH Keywords: set packings
MaRDI profile type: Publication
full work available at URL: s00453-022-00986-0
OpenAlex ID: W2990007591
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
cites work: Reducibility among Combinatorial Problems
cites work: Fundamentals of parameterized complexity
cites work: Parametrized complexity theory.
cites work: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
cites work: Q6059165
cites work: Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
cites work: A top-down approach to search-trees: Improved algorithmics for 3-hitting set
cites work: Iterative compression and exact algorithms
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: Dynamic Parameterized Problems and Algorithms
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Towards optimal and expressive kernelization for \(d\)-hitting set
cites work: Nondeterminism within $P^ * $
cites work: Maintaining minimum spanning forests in dynamic graphs
cites work: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
cites work: Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
cites work: Dyn-FO: A parallel, dynamic complexity class
cites work: Reachability Is in DynFO
cites work: Fast Dynamic Graph Algorithms for Parameterized Problems
cites work: The vectorization of ITPACK 2C
cites work: Q4263467
cites work: Q3219751
cites work: Intersection Theorems for Systems of Sets
cites work: Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
cites work: Parameterized approximation via fidelity preserving transformations
cites work: Lossy kernelization
DOI: 10.1007/S00453-022-00986-0
description: scientific article; zbMATH DE number 7608296