Skip to Main content Skip to Navigation
New interface
Conference papers

A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs

Sangsoo Park 1 Sung Gwan Park 1 Bastien Cazaux 2 Kunsoo Park 3 Eric Rivals 2 
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 : Tuesday, September 13, 2022 - 3:01:11 PM
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 Gwan Park, Bastien Cazaux, Kunsoo Park, Eric Rivals. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs. CPM 2021 - 32nd Annual Symposium on Combinatorial Pattern Matching, 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