A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2021

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).
Fichier principal
Vignette du fichier
LIPIcs-CPM-2021-22.pdf (881.82 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03431830 , version 1 (16-11-2021)

Licence

Identifiers

Cite

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⟩
42 View
28 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More