Solving SCS for bounded length strings in fewer than \(2^n\) steps

DOI10.1016/j.ipl.2014.03.004zbMath1296.68203OpenAlexW2093445940MaRDI QIDQ2448115

Ivan Mihajlin, Alexander Golovnev, Alexander S. Kulikov

Publication date: 30 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.03.004

zbMATH Keywords

traveling salesman problemexact algorithmNP-hard problemexponential-time algorithmshortest common superstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (4)

Rural postman parameterized by the number of components of required edges ⋮ Parameterized complexity of superstring problems ⋮ Collapsing Superstring Conjecture ⋮ Hierarchical overlap graph

Cites Work

• A finite-difference sieve to count paths and cycles by length
• Optimal 2-constraint satisfaction via sum-product algorithms
• On finding minimal length superstrings
• Dynamic programming meets the principle of inclusion and exclusion
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Trimmed Moebius inversion and graphs of bounded degree
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Solving 3-Superstring in 3 n/3 Time
• New upper bounds for the problem of maximal satisfiability
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• Set Partitioning via Inclusion-Exclusion
• An algorithm for the Rural Postman problem on a directed graph
• 3-coloring in time
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree
• A full derandomization of schöning's k-SAT algorithm
• Mathematical Foundations of Computer Science 2005
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• Lyndon Words and Short Superstrings
• MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in $\mathcal{O}(2^n)$ Time

This page was built for publication: Solving SCS for bounded length strings in fewer than \(2^n\) steps