1 citations · 1 across the 9 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
A Tight Cycle-Cover Inequality for Shortest Common Superstring
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin +1
In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best…
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.…