2020/08/20 by Marcel Wild, Wild, Marcel
Computer Science · #Algorithms and Data Compression #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2008.08996
openalex publication_date 2020/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Our main objective is the COMPRESSED enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author's best knowledge the only previous attempt towards compression, due to Toda, is based on BDD's and much different from our techniques. Numerical experiments show that traditional one-by-one enumeration schemes cannot compete against compressed enumeration when the degree of compression is high. Our method works particularly well in these two cases: Either compressing all e x a c t hitting sets, or all m i n i m u m - cardinality hitting sets. In many aspects this version is better structured than its predecessor, and also contains some new material (such as an application of Rado's Theorem).