Hierarchical overlap graph

DOI10.1016/j.ipl.2019.105862zbMath1478.68222arXiv1802.04632OpenAlexW2984805838WikidataQ126798634 ScholiaQ126798634MaRDI QIDQ2281159

Bastien Cazaux, Eric Rivals

Publication date: 19 December 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.04632

zbMATH Keywords

online algorithmsdata structuressuperstringassemblyAho-Corasik

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items (3)

All-pairs suffix/prefix in optimal time using Aho-Corasick space ⋮ Collapsing Superstring Conjecture ⋮ A tale of optimizing the space taken by de Bruijn graphs

Uses Software

• Readjoiner

Cites Work

• Approximate all-pairs suffix/prefix overlaps
• A linear-time algorithm for finding approximate shortest common superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• An efficient algorithm for the all pairs suffix-prefix problem
• A fast algorithm for the all-pairs suffix-prefix problem
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• An improved algorithm for the all-pairs suffix-prefix problem
• A linear time algorithm for shortest cyclic cover of strings
• Efficient string matching
• Linear approximation of shortest superstrings
• Practical lower and upper bounds for the Shortest Linear Superstring

This page was built for publication: Hierarchical overlap graph