Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492909zbMATH OpenOpenAlexFDO

Authors Virginia Vassilevska Williams

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Approximating Shortest Superstrings
• scientific article; zbMATH DE number 1420898
• Sequential and Parallel Approximation of Shortest Superstrings
• Improved length bounds for the shortest superstring problem
• A 2_3² superstring approximation algorithm

Cited in

(16)

• Why greed works for shortest common superstring problem
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• A linear time algorithm for shortest cyclic cover of strings
• A survey on combinatorial optimization in dynamic environments
• Applying Small-Scale DNA Signatures as an Aid in Assembling Soybean Chromosome Sequences
• A Probabilistic PTAS for Shortest Common Superstring
• Why Greed Works for Shortest Common Superstring Problem
• Reoptimization of the Shortest Common Superstring Problem
• A probabilistic PTAS for shortest common superstring
• Approximating shortest superstring problem using de Bruijn graphs
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring
• Restricted and swap common superstring: a multivariate algorithmic perspective
• Practical lower and upper bounds for the shortest linear superstring
• Superstrings with multiplicities
• Reoptimization of the shortest common superstring problem
• Approximation guarantees for shortest superstrings: simpler and better

This page was built for publication: Mathematical Foundations of Computer Science 2005

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