HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Efficient Construction of Hierarchical Overlap Graphs

Abstract : The hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in O(||P || + n 2) time and O(||P || + n × min(n, max{|s| : s ∈ P })) space, where ||P || is the sum of lengths of the n strings in P. We present a new algorithm of O(||P || log n) time and O(||P ||) space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using O(||P || log n log log n) time and O(||P ||) space in the word RAM model of computation.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Thursday, November 19, 2020 - 1:35:41 PM
Last modification on : Tuesday, May 3, 2022 - 6:26:04 PM
Long-term archiving on: : Saturday, February 20, 2021 - 7:17:19 PM


Files produced by the author(s)




Sung Park, Bastien Cazaux, Kunsoo Park, Eric Rivals. Efficient Construction of Hierarchical Overlap Graphs. 27th International Symposium on String Processing and Information Retrieval (SPIRE), Oct 2020, Orlando, FL, United States. pp.277-290, ⟨10.1007/978-3-030-59212-7_20⟩. ⟨lirmm-03014336⟩



Record views


Files downloads