Efficiently enumerating hitting sets of hypergraphs arising in data profiling
DOI10.1016/j.jcss.2021.10.002zbMath1478.68219OpenAlexW2908441505MaRDI QIDQ2051864
Thomas Bläsius, Kitty Meeks, Julius Lischeid, Tobias Friedrich, Martin Schirneck
Publication date: 25 November 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://eprints.gla.ac.uk/172038/7/172038.pdf
transversal hypergraphenumeration algorithmdata profilingminimal hitting setunique column combinationW[3-completeness]
Analysis of algorithms and problem complexity (68Q25) 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) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- On the max min vertex cover problem
- On the computational complexity of upper fractional domination
- A global parallel algorithm for the hypergraph transversal problem
- Strong computational lower bounds via parameterized complexity
- On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
- Computational aspects of monotone dualization: a brief survey
- On the parameterized complexity of multiple-interval graph problems
- A theory of diagnosis from first principles
- On generating all maximal independent sets
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Which problems have strongly exponential complexity?
- The many facets of upper domination
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Incremental delay enumeration: space and time
- Extension of some edge graph problems: standard and parameterized complexity
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Parametrized complexity theory.
- Complexity of identification and dualization of positive Boolean functions
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- On generating all solutions of generalized satisfiability problems
- Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Dual subimplicants of positive Boolean functions
- Engineering Motif Search for Large Graphs
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
- About Keys of Formal Context and Conformal Hypergraph
- Parameterized Algorithms
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- SOFSEM 2005: Theory and Practice of Computer Science
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- On the complexity of \(k\)-SAT
