Efficiently enumerating hitting sets of hypergraphs arising in data profiling
type: Item
instance of: scholarly article
title: Efficiently enumerating hitting sets of hypergraphs arising in data profiling
zbMATH Open document ID: 1478.68219
author: Thomas Bläsius
author: Tobias Friedrich
author: Julius Lischeid
author: Kitty Meeks
author: Martin Schirneck
published in: Journal of Computer and System Sciences
publication date: 2021-11-25T00:00:00Z
full work available at URL: 172038.pdf
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7433362
zbMATH Keywords: data profiling
zbMATH Keywords: enumeration algorithm
zbMATH Keywords: minimal hitting set
zbMATH Keywords: transversal hypergraph
zbMATH Keywords: unique column combination
zbMATH Keywords: W[3]-completeness
MaRDI profile type: Publication
OpenAlex ID: W2908441505
cites work: The many facets of upper domination
cites work: Q3993087
cites work: Q4088860
cites work: Complexity of identification and dualization of positive Boolean functions
cites work: Engineering Motif Search for Large Graphs
cites work: Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
cites work: Q4634389
cites work: On the max min vertex cover problem
cites work: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
cites work: Dual subimplicants of positive Boolean functions
cites work: Incremental delay enumeration: space and time
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: Extension of some edge graph problems: standard and parameterized complexity
cites work: Extension of Vertex Cover and Independent Set in some classes of graphs
cites work: Strong computational lower bounds via parameterized complexity
cites work: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
cites work: On the computational complexity of upper fractional domination
cites work: About Keys of Formal Context and Conformal Hypergraph
cites work: On generating all solutions of generalized satisfiability problems
cites work: Parameterized Algorithms
cites work: Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
cites work: Q3805968
cites work: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
cites work: Fundamentals of parameterized complexity
cites work: Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
cites work: Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
cites work: Identifying the Minimal Transversals of a Hypergraph and Related Problems
cites work: New Results on Monotone Dualization and Generating Hypergraph Transversals
cites work: Computational aspects of monotone dualization: a brief survey
cites work: Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: SOFSEM 2005: Theory and Practice of Computer Science
cites work: Parametrized complexity theory.
cites work: On the Complexity of Dualization of Monotone Disjunctive Normal Forms
cites work: Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
cites work: How to assign votes in a distributed system
cites work: Q4386975
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: On generating all maximal independent sets
cites work: A global parallel algorithm for the hypergraph transversal problem
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
cites work: Q5226843
cites work: Q5710169
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: A theory of diagnosis from first principles
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Q5368736
DOI: 10.1016/J.JCSS.2021.10.002
description: scientific article; zbMATH DE number 7433362