A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs

Sangsoo Park, Sung Gwan Park, Bastien Cazaux +2

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|| l…