Efficiently enumerating hitting sets of hypergraphs arising in data profiling
From MaRDI portal
Publication:2051864
data profilingenumeration algorithmminimal hitting settransversal hypergraphunique column combinationW[3-completeness]
Enumeration in graph theory (05C30) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- An Efficient Algorithm for the Transversal Hypergraph Generation
- Faster Algorithms to Enumerate Hypergraph Transversals
Cites work
- A global parallel algorithm for the hypergraph transversal problem
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- A theory of diagnosis from first principles
- About Keys of Formal Context and Conformal Hypergraph
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Completeness for first-order properties on sparse structures with algorithmic applications
- Complexity of identification and dualization of positive Boolean functions
- Computational aspects of monotone dualization: a brief survey
- Dual subimplicants of positive Boolean functions
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Efficient enumeration of solutions produced by closure operations
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Engineering Motif Search for Large Graphs
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Extension of some edge graph problems: standard and parameterized complexity
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Fundamentals of parameterized complexity
- How to assign votes in a distributed system
- scientific article; zbMATH DE number 4074550 (Why is no real title available?)
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- scientific article; zbMATH DE number 3508549 (Why is no real title available?)
- scientific article; zbMATH DE number 1149451 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Incremental delay enumeration: space and time
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On generating all maximal independent sets
- On generating all solutions of generalized satisfiability problems
- On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
- On the complexity of k-SAT
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the computational complexity of upper fractional domination
- On the max min vertex cover problem
- On the parameterized complexity of multiple-interval graph problems
- Parameterized algorithms
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- Parametrized complexity theory.
- SOFSEM 2005: Theory and Practice of Computer Science
- Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
- Strong computational lower bounds via parameterized complexity
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- The many facets of upper domination
- The parameterized complexity of dependency detection in relational databases
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Which problems have strongly exponential complexity?
Cited in
(12)- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems
- Enumerating minimal defensive alliances
- Enumerating minimal connected dominating sets
- Enumerating minimal solution sets for metric graph problems
- Enumerating minimal connected dominating sets
- Roman hitting functions
- Monomial polarization and depolarization of abstract simplicial complexes
- Solving one-sided linear systems over symmetrized and supertropical semirings
- Enumeration of minimal hitting sets parameterized by treewidth
- Enumerating minimal dominating sets and variants in chordal bipartite graphs
This page was built for publication: Efficiently enumerating hitting sets of hypergraphs arising in data profiling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051864)
