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

A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs

Abstract : The hierarchical overlap graph (HOG) is a graph that encodes overlaps from a given set P of n strings, as the overlap graph does. A best known algorithm constructs HOG in O(||P || log n) time and O(||P ||) space, where ||P || is the sum of lengths of the strings in P. In this paper we present a new algorithm to construct HOG in O(||P ||) time and space. Hence, the construction time and space of HOG are better than those of the overlap graph, which are O(||P || + n 2).
Complete list of metadata

Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2021 - 10:53:24 PM
Last modification on : Thursday, November 18, 2021 - 3:56:35 AM
Long-term archiving on: : Thursday, February 17, 2022 - 9:30:50 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Sangsoo Park, Sung Park, Bastien Cazaux, Kunsoo Park, Eric Rivals. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs. 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), Institute of Computer Science of University of Wrocław, Poland., Jul 2021, Wrocław, Poland. pp.22:1--22:9, ⟨10.4230/LIPIcs.CPM.2021.22⟩. ⟨lirmm-03431830⟩



Record views


Files downloads