Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling

DOI10.1137/1.9781611975499.11zbMath1430.68178arXiv1805.01310OpenAlexW3210187043MaRDI QIDQ5232759

Tobias Friedrich, Thomas Bläsius, Martin Schirneck, Kitty Meeks, Julius Lischeid

Publication date: 13 September 2019

Published in: 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Database theory (68P15) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Unnamed Item ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ The complexity of dependency detection and discovery in relational databases ⋮ On the complexity of solution extension of optimization problems ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems