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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03431830
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

File

LIPIcs-CPM-2021-22.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

9

Files downloads

3