| Publication | Date of Publication | Type |
|---|
| Optimal near-linear space heaviest induced ancestors | 2024-10-21 | Paper |
| Compressed indexing for consecutive occurrences | 2024-10-21 | Paper |
| Order-preserving squares in strings | 2024-10-21 | Paper |
| Slowing down top trees for better worst-case compression | 2024-10-07 | Paper |
| Minimum cut in \(O(m \log^2 n)\) time | 2024-10-07 | Paper |
| Finding the KT partition of a weighted graph in near-linear time | 2024-08-22 | Paper |
| Streaming regular expression membership and pattern matching | 2024-07-19 | Paper |
| Pattern matching on grammar-compressed strings in linear time | 2024-07-19 | Paper |
| Sublinear dynamic interval scheduling (on One or Multiple Machines) | 2024-06-24 | Paper |
| Enumerating \(m\)-length walks in directed graphs with constant delay | 2024-05-31 | Paper |
| Sorting signed permutations by reversals in nearly-linear time | 2024-05-29 | Paper |
| On the number of factors in the LZ-End factorization | 2024-05-29 | Paper |
| Optimal square detection over general alphabets | 2024-05-14 | Paper |
| A note on a recent algorithm for minimum cut | 2024-05-14 | Paper |
| Simpler adjacency labeling for planar graphs with B-Trees | 2024-05-14 | Paper |
| Faster exponential algorithm for permutation pattern matching | 2024-05-14 | Paper |
| The dynamic \(k\)-mismatch problem | 2024-05-06 | Paper |
| Minimal absent words in rooted and unrooted trees | 2024-04-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147386 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147419 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6065428 | 2023-11-14 | Paper |
| Fully dynamic approximation of LIS in polylogarithmic time | 2023-11-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6065422 | 2023-11-14 | Paper |
| A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem | 2023-11-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6168464 | 2023-08-08 | Paper |
| On the hardness of computing the edit distance of shallow trees | 2023-08-04 | Paper |
| Matching patterns with variables under edit distance | 2023-08-04 | Paper |
| Better distance labeling for unweighted planar graphs | 2023-06-05 | Paper |
| Tight bound for the number of distinct palindromes in a tree | 2023-05-16 | Paper |
| Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can) | 2023-04-26 | Paper |
| Existential length universality | 2023-02-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5874289 | 2023-02-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5874431 | 2023-02-07 | Paper |
| On Indeterminate Strings Matching. | 2023-02-07 | Paper |
| Top Tree Compression of Tries. | 2023-02-03 | Paper |
| The Theory of Universal Graphs for Infinite Duration Games | 2022-10-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5092429 | 2022-07-21 | Paper |
| Even faster elastic-degenerate string matching via fast matrix multiplication | 2022-07-21 | Paper |
| Quasi-Periodicity in Streams | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5088888 | 2022-07-18 | Paper |
| Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games | 2022-07-18 | Paper |
| Streaming Dictionary Matching with Mismatches | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090479 | 2022-07-18 | Paper |
| Lower bounds for the number of repetitions in 2D strings | 2022-06-15 | Paper |
| Elastic-Degenerate String Matching via Fast Matrix Multiplication | 2022-06-08 | Paper |
| Fault-tolerant distance labeling for planar graphs | 2022-05-10 | Paper |
| Incomplete directed perfect phylogeny in linear time | 2022-03-25 | Paper |
| Strictly in-place algorithms for permuting and inverting permutations | 2022-03-25 | Paper |
| Better distance labeling for unweighted planar graphs | 2022-03-25 | Paper |
| Fault-tolerant distance labeling for planar graphs | 2022-03-22 | Paper |
| Streaming dictionary matching with mismatches | 2022-03-22 | Paper |
| Fast and longest rollercoasters | 2022-03-22 | Paper |
| Top tree compression of tries | 2022-01-18 | Paper |
| Edit distance with block operations | 2021-08-04 | Paper |
| Near-optimal distance emulator for planar graphs | 2021-08-04 | Paper |
| Fast entropy-bounded string dictionary look-up with mismatches | 2021-08-04 | Paper |
| A faster construction of greedy consensus trees | 2021-07-28 | Paper |
| Edit distance between unrooted trees in cubic time | 2021-07-28 | Paper |
| Improved bounds for shortest paths in dense distance graphs | 2021-07-28 | Paper |
| A faster FPTAS for \#Knapsack | 2021-07-28 | Paper |
| Towards unified approximate pattern matching for Hamming and \(L_1\) distance | 2021-07-28 | Paper |
| Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search | 2021-05-03 | Paper |
| Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time | 2021-04-14 | Paper |
| Distinct squares in circular words | 2021-02-16 | Paper |
| Block trees | 2021-02-02 | Paper |
| Tight upper and lower bounds on suffix tree breadth | 2021-01-25 | Paper |
| All non-trivial variants of 3-LDT are equivalent | 2021-01-19 | Paper |
| Slowing down top trees for better worst-case compression | 2020-12-16 | Paper |
| Dispersion on trees | 2020-05-27 | Paper |
| A family of approximation algorithms for the maximum duo-preservation string mapping problem | 2020-05-25 | Paper |
| Universal reconstruction of a string | 2020-02-20 | Paper |
| Computing quartet distance is equivalent to counting 4-cycles | 2020-01-30 | Paper |
| Almost optimal distance oracles for planar graphs | 2020-01-30 | Paper |
| Tight tradeoffs for real-time approximation of longest palindromes in streams | 2019-08-20 | Paper |
| Hide and seek with repetitions | 2019-01-25 | Paper |
| Bookmarks in grammar-compressed strings | 2018-10-17 | Paper |
| Limit behavior of the multi-agent rotor-router system | 2018-08-24 | Paper |
| Sublinear-space distance labeling using hubs | 2018-08-16 | Paper |
| Speeding up dynamic programming in the line-constrained \(k\)-median | 2018-08-03 | Paper |
| Sparse suffix tree construction in optimal time and space | 2018-07-16 | Paper |
| LZ77 factorisation of trees | 2018-04-19 | Paper |
| Labeling schemes for nearest common ancestors through minor-universal trees | 2018-03-15 | Paper |
| Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time | 2018-03-15 | Paper |
| Better tradeoffs for exact distance oracles in planar graphs | 2018-03-15 | Paper |
| Near-optimal compression for the planar graph metric | 2018-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4607988 | 2018-03-15 | Paper |
| Tree edit distance cannot be computed in strongly subcubic time (unless APSP can) | 2018-03-15 | Paper |
| Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets | 2018-03-01 | Paper |
| The nearest colored node in a tree | 2018-02-16 | Paper |
| Efficiently finding all maximal \(\alpha\)-gapped repeats | 2018-01-24 | Paper |
| Validating the Knuth-Morris-Pratt failure function, fast and online | 2017-11-07 | Paper |
| Randomized algorithms for finding a majority element | 2017-10-17 | Paper |
| Faster longest common extension queries in strings over general alphabets | 2017-10-17 | Paper |
| Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. | 2017-10-17 | Paper |
| The nearest colored node in a tree | 2017-10-17 | Paper |
| Optimal distance labeling schemes for trees | 2017-10-11 | Paper |
| Wavelet trees meet suffix trees | 2017-10-05 | Paper |
| Brief announcement: Sublinear-space distance labeling using hubs | 2017-09-29 | Paper |
| Optimal pattern matching in LZW compressed strings | 2017-09-29 | Paper |
| Optimal query time for encoding range majority | 2017-09-22 | Paper |
| Testing generalised freeness of words | 2017-03-03 | Paper |
| Finding pseudo-repetitions | 2017-01-30 | Paper |
| Speeding up dynamic programming in the line-constrained \(k\)-median | 2016-09-29 | Paper |
| Longest common extensions in trees | 2016-06-16 | Paper |
| Computing minimal and maximal suffixes of a substring | 2016-06-16 | Paper |
| Order-preserving pattern matching with \(k\) mismatches | 2016-06-16 | Paper |
| Approximating LZ77 via Small-Space Multiple-Pattern Matching | 2015-11-19 | Paper |
| Universal reconstruction of a string | 2015-10-30 | Paper |
| Submatrix maximum queries in Monge matrices are equivalent to predecessor search | 2015-10-27 | Paper |
| Optimal encodings for range top-\(k\), selection, and min-max | 2015-10-27 | Paper |
| Computing the Longest Unbordered Substring | 2015-10-02 | Paper |
| Longest \(\alpha \)-gapped repeat and palindrome | 2015-09-29 | Paper |
| Strong inapproximability of the shortest reset word | 2015-09-16 | Paper |
| Euclidean TSP with few inner points in linear space | 2015-09-11 | Paper |
| Encodings of range maximum-sum segment queries and applications | 2015-08-20 | Paper |
| Longest common extensions in trees | 2015-08-20 | Paper |
| Alphabet-dependent string searching with wexponential search trees | 2015-08-20 | Paper |
| Approximate pattern matching in LZ77-compressed texts | 2015-05-04 | Paper |
| Optimal pattern matching in LZW compressed strings | 2014-12-05 | Paper |
| Weighted ancestors in suffix trees | 2014-10-08 | Paper |
| Improved submatrix maximum queries in Monge matrices | 2014-07-01 | Paper |
| Computing minimal and maximal suffixes of a substring revisited | 2014-06-30 | Paper |
| Order-preserving pattern matching with \(k\) mismatches | 2014-06-30 | Paper |
| Simple and efficient LZW-compressed multiple pattern matching | 2014-04-01 | Paper |
| LZ77-based self-indexing with faster pattern matching | 2014-03-31 | Paper |
| Beating \(O(nm)\) in approximate LZW-compressed pattern matching | 2014-01-14 | Paper |
| Minimal Discriminating Words Problem Revisited | 2013-10-29 | Paper |
| Discovering hidden repetitions in words | 2013-08-05 | Paper |
| Converting SLP to LZ78 in almost Linear Time | 2013-06-14 | Paper |
| Alphabetic minimax trees in linear time | 2013-06-14 | Paper |
| Minimax trees in linear time with applications | 2012-11-15 | Paper |
| Tying up the loose ends in fully LZW-compressed pattern matching | 2012-08-23 | Paper |
| Simple and efficient LZW-compressed multiple pattern matching | 2012-08-14 | Paper |
| A faster grammar-based self-index | 2012-06-08 | Paper |
| Faster approximate pattern matching in compressed repetitive texts | 2011-12-16 | Paper |
| Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic | 2011-09-16 | Paper |
| On minimising automata with errors | 2011-08-17 | Paper |
| Chrobak normal form revisited, with applications | 2011-07-29 | Paper |
| Finding the growth rate of a regular or context-free language in polynomial time | 2010-09-06 | Paper |
| Validating the Knuth-Morris-Pratt failure function, fast and online | 2010-06-22 | Paper |
| Grammar-Based Compression in a Streaming Model | 2010-05-26 | Paper |
| On the problem of freeness of multiplicative matrix semigroups | 2010-03-09 | Paper |
| Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks | 2010-02-26 | Paper |
| Minimax Trees in Linear Time with Applications | 2009-12-11 | Paper |
| Hyper-minimisation Made Efficient | 2009-10-16 | Paper |
| 2-Synchronizing Words | 2008-11-20 | Paper |
| Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time | 2008-10-30 | Paper |
| A Combinatorial Approach to Collapsing Words | 2007-09-05 | Paper |
| Optimal Bounds for Distinct Quartics | N/A | Paper |
