Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345zbMATH Open1156.68394OpenAlexW2494705596MaRDI QIDQ5492909FDOQ5492909

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

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^2\) superstring approximation algorithm

Mathematics Subject Classification ID

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

Cited In (16)

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

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)