 |
HAL-LIRMM - Open Archive |  |
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).
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
Long-term archiving on: : Thursday, February 17, 2022 - 9:30:50 PM
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
File
LIPIcs-CPM-2021-22.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License