2026-07-25T03:01:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13973 2024-03-06T10:53:02Z ddc:004 open_access

A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs Park, Sangsoo Park, Sung Gwan Cazaux, Bastien Park, Kunsoo Rivals, Eric overlap graph hierarchical overlap graph shortest superstring problem border array 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²). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sangsoo Park and Sung Gwan Park and Bastien Cazaux and Kunsoo Park and Eric Rivals 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.22 urn:nbn:de:0030-drops-139736 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.22 eng https://creativecommons.org/licenses/by/4.0/legalcode