Solving SCS for bounded length strings in fewer than 2ⁿ steps

DOI10.1016/J.IPL.2014.03.004MaRDI QIDQ2448115zbMATH OpenOpenAlexFDO

Authors Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin

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

exact algorithmexponential-time algorithmNP-hard problemshortest common superstringtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Solving 3-superstring in \(3^{n/3}\) time
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• More on the complexity of common superstring and supersequence problems
• Improved length bounds for the shortest superstring problem
• Approximation algorithms for the shortest common superstring problem

Cites work

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

Cited in

(4)

• Hierarchical overlap graph
• Solving 3-superstring in \(3^{n/3}\) time
• Rural postman parameterized by the number of components of required edges
• Collapsing Superstring Conjecture

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448115)