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).
https://hal-lirmm.ccsd.cnrs.fr/lirmm-03431830 Contributor : Eric RivalsConnect 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
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⟩