1 citations · 2 across the 4 of their papers we have counts for
8 papers
Internal Shortest Absent Word Queries in Constant Time and Linear Space
Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov +1
Given a string of length over an alphabet of size , we are to preprocess so that given a range , we can return a representa…
Weighted Ancestors in Suffix Trees Revisited
Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi +1
The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require time for queries provided $O(n\mathop{\math…
Optimal Skeleton Huffman Trees Revisited
Dmitry Kosolobov, Oleg Merkurev
A skeleton Huffman tree is a Huffman tree in which all disjoint maximal perfect subtrees are shrunk into leaves. Skeleton Huffman trees, besides saving storage space, are also used…
Lempel-Ziv-like Parsing in Small Space
Dmitry Kosolobov, Daniel Valenzuela, Gonzalo Navarro +1
Lempel-Ziv (LZ77 or, briefly, LZ) is one of the most effective and widely-used compressors for repetitive texts. However, the existing efficient methods computing the exact LZ pars…
Compressed Multiple Pattern Matching
Dmitry Kosolobov, Nikita Sivukhin
Given strings over the alphabet , the classical Aho--Corasick data structure allows us to find all occurrences of the strings in any text in $O(…
Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov +1
Given a threshold and a set of haplotype sequences, each having length , the minimum segmentation problem for founder reconstruction…