Skip to Main content Skip to Navigation
Conference papers

A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs

Sangsoo Park 1 Sung Park 1 Bastien Cazaux 2 Kunsoo Park 3 Eric Rivals 2
1 Samsung Electronics [Korea]
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 SNU - Seoul National University [Seoul]
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).
Keywords : overlap graph border array shortest superstring problem hierarchical overlap graph
Document type :
Conference papers
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

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

Licence

Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

LIRMM | MAB | TDS-MACS | MIPS | UNIV-MONTPELLIER | ANR | CNRS

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

9

Files downloads

3