Efficient Construction of Hierarchical Overlap Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2020

Efficient Construction of Hierarchical Overlap Graphs

Abstract

The hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in O(||P || + n 2) time and O(||P || + n × min(n, max{|s| : s ∈ P })) space, where ||P || is the sum of lengths of the n strings in P. We present a new algorithm of O(||P || log n) time and O(||P ||) space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using O(||P || log n log log n) time and O(||P ||) space in the word RAM model of computation.
Fichier principal
Vignette du fichier
Efficient_Construction_of_Hierarchical_Overlap_Graphs(1).pdf (591 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-03014336 , version 1 (19-11-2020)

Identifiers

Cite

Sung Gwan Park, Bastien Cazaux, Kunsoo Park, Eric Rivals. Efficient Construction of Hierarchical Overlap Graphs. SPIRE 2020 - 27th International Symposium on String Processing and Information Retrieval, Oct 2020, Orlando, FL, United States. pp.277-290, ⟨10.1007/978-3-030-59212-7_20⟩. ⟨lirmm-03014336⟩
58 View
198 Download

Altmetric

Share

Gmail Facebook X LinkedIn More