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


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