2 citations · 3 across the 13 of their papers we have counts for
5 papers · 1 filter
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…
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.…
Improved Quantum Algorithms for Subset Sum and -SUM
Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1
The Subset Sum problem asks whether, given integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is (Horo…
If Edge Coloring is Hard under SETH, then SETH is False
Alexander S. Kulikov, Ivan Mihajlin
The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time (let alone ), where is the number of nodes of the inp…
Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy
Grigorii Braulov, Nikolai Chukhin, Alexander S. Kulikov +1
The graph homomorphism problem HOM is: given an -vertex source graph and an -vertex target graph , is there a mapping from to that preserves edges? A str…