Approximating Shortest Superstring Problem Using de Bruijn Graphs

DOI10.1007/978-3-642-38905-4_13zbMath1382.68349OpenAlexW194848955MaRDI QIDQ4928566

Alexander Golovnev, Ivan Mihajlin, Alexander S. Kulikov

Publication date: 14 June 2013

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38905-4_13

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (7)

A linear time algorithm for shortest cyclic cover of strings ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Collapsing Superstring Conjecture ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree ⋮ Practical lower and upper bounds for the Shortest Linear Superstring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The greedy algorithm for shortest superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Approximation algorithms for the shortest common superstring problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• An algorithm for the Rural Postman problem on a directed graph
• P-Complete Approximation Problems
• Rotations of Periodic Strings and Short Superstrings
• An Eulerian path approach to DNA fragment assembly
• Arc Routing Problems, Part II: The Rural Postman Problem
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Parallel and sequential approximation of shortest superstrings
• Improved length bounds for the shortest superstring problem
• Mathematical Foundations of Computer Science 2005
• Lyndon Words and Short Superstrings

This page was built for publication: Approximating Shortest Superstring Problem Using de Bruijn Graphs