Summary: 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(\vert \vert P \vert \vert + n^2)\) time and \(O(\vert \vert P \vert \vert +n\times \min (n,\max \{|s|:s\in P\}))\) space, where \(\vert \vert P \vert \vert\) is the sum of lengths of the \(n\) strings in \(P\). We present a new algorithm of \(O(\vert \vert P \vert \vert \log n)\) time and \(O(\vert \vert P \vert \vert )\) space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using \(O(\vert \vert P \vert \vert \frac{\log n}{\log \log n})\) time and \(O(\vert \vert P \vert \vert )\) space in the word RAM model of computation.
For the entire collection see [Zbl 1502.68020].