3 papers
cs.DS2026
The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1
In the Shortest Common Superstring (SCS) problem, one is given a set of strings and is asked to find a string of minimum length containing each of the input strings as a substring.…
cs.CC2023
Proving Unsatisfiability with Hitting Formulas
Yuval Filmus, Edward A. Hirsch, Artur Riazanov +2
Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultane…
math.CO2022
Irreducible subcube partitions
Yuval Filmus, Edward Hirsch, Sascha Kurz +4
A \emph{subcube partition} is a partition of the Boolean cube into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are…