Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
From MaRDI portal
Publication:6078297
DOI10.1016/j.jcss.2023.103479arXiv2109.06042OpenAlexW3199867152MaRDI QIDQ6078297
Daniel A. Skachkov, Artem M. Kirilin, O. Yu. Tsidulko, Pavel V. Smirnov, René van Bevern
Publication date: 24 October 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.06042
data reductionparallel algorithmcomputational experimentNP-hard problemparameterized complexityGPUproblem kernelization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exploiting a hypergraph model for finding Golomb rulers
- Complexity of conflict-free colorings of graphs
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- An efficient fixed-parameter algorithm for 3-hitting set
- Exploiting hidden structure in selecting dimensions that distinguish vectors
- Fixed-parameter algorithms for cluster vertex deletion
- A kernelization algorithm for \(d\)-hitting set
- A theory of diagnosis from first principles
- A note on perfect orders
- Algorithmic meta-theorems for restrictions of treewidth
- Recognition algorithms for orders of small width and graphs of small Dilworth number
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Dynamic kernels for hitting sets and set packing
- Parameterized complexity of happy coloring problems
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- The power of linear-time data reduction for maximum matching
- On pairwise compatibility graphs having Dilworth number \(k\)
- Strong inconsistency
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Parametrized complexity theory.
- A decomposition theorem for partially ordered sets
- Streaming Kernelization
- Presolve Reductions in Mixed Integer Programming
- A taxonomy of problems with fast parallel algorithms
- The Dilworth Number of a Graph
- Kernelization Lower Bounds Through Colors and IDs
- Reducibility among Combinatorial Problems
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
- The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment
- Computational Complexity
- An Annotated Glossary of Graph Theory Parameters, with Conjectures
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Dynamic Parameterized Problems and Algorithms
- On data reduction for dynamic vector bin packing
