Practical lower and upper bounds for the shortest linear superstring

DOI10.4230/LIPICS.SEA.2018.18MaRDI QIDQ5140730zbMATH OpenOpenAlexFDO

Authors Bastien Cazaux, Samuel Juhel, Eric Rivals

Publication date 16 December 2020

Full work available at URL https://doi.org/10.4230/lipics.sea.2018.18

zbMATH Keywords

overlapapproximationgreedylinear timecyclic covertext compressionconcat-cycles

Mathematics Subject Classification ID

Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Linear approximation of shortest superstrings
• Mathematical Foundations of Computer Science 2005
• A 2_3² superstring approximation algorithm
• The shortest common superstring problem: average case analysis for both exact and approximate matching
• Approximating Shortest Superstrings

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• A linear time algorithm for shortest cyclic cover of strings
• A linear-time algorithm for finding approximate shortest common superstrings
• A note on shortest superstrings with flipping
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Algorithms on Strings, Trees and Sequences
• Approximating shortest superstring problem using de Bruijn graphs
• Combinatorial algorithms for DNA sequence assembly
• Efficient string matching
• Linear approximation of shortest superstrings
• Lyndon words and short superstrings
• Mathematical Foundations of Computer Science 2005
• On the Greedy Superstring Conjecture
• On the greedy algorithm for the shortest common superstring problem with reversals
• Superstrings with multiplicities
• The shortest superstring problem
• Why greed works for shortest common superstring problem

Cited in

(5)

• Collapsing Superstring Conjecture
• Hierarchical overlap graph
• Superstrings with multiplicities
• Sequential and Parallel Approximation of Shortest Superstrings
• All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent

This page was built for publication: Practical lower and upper bounds for the shortest linear superstring

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