A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
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).
8 pages, 2 figures, submitted to CPM 2021
- University of Montpellier France
- Leibniz Association Germany
- Montpellier Laboratory of Informatics, Robotics and Microelectronics France
- French National Centre for Scientific Research France
- Samsung (South Korea) Korea (Republic of)
FOS: Computer and information sciences, hierarchical overlap graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], overlap graph, [INFO] Computer Science [cs], 004, 510, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Theory of computation → Pattern matching, shortest superstring problem, border array, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM], ddc: ddc:004
FOS: Computer and information sciences, hierarchical overlap graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], overlap graph, [INFO] Computer Science [cs], 004, 510, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Theory of computation → Pattern matching, shortest superstring problem, border array, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM], ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!