Publications
Detailed Information
A linear time algorithm for constructing hierarchical overlap graphs
Cited 0 time in
Web of Science
Cited 3 time in Scopus
- Authors
- Issue Date
- 2021-07
- Citation
- Leibniz International Proceedings in Informatics, Vol.191
- Abstract
- © Sangsoo Park, Sung Gwan Park, Bastien Cazaux, Kunsoo Park, and Eric Rivals.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|| + n2).
- ISSN
- 1868-8969
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.