| Publication | Date of Publication | Type |
|---|
| Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity | 2026-05-26 | Paper |
| An almost optimal edit distance oracle | 2026-05-12 | Paper |
| Efficiently testing Simon's congruence | 2026-04-21 | Paper |
| Minimum cut in O(m^2 n time | 2026-03-18 | Paper |
| Dynamic longest common substring in polylogarithmic time | 2026-03-18 | Paper |
On the complexity of indeterminate strings matching
Theoretical Computer Science | 2026-02-27 | Paper |
| Optimal bounds for distinct quartics | 2026-01-14 | Paper |
| Online context-free recognition in OMv time | 2025-12-02 | Paper |
| Faster sliding window string indexing in streams | 2025-12-02 | Paper |
| Cut query algorithms with star contraction | 2025-08-15 | Paper |
| Substring complexity in sublinear space | 2025-07-24 | Paper |
Almost optimal exact distance oracles for planar graphs
Journal of the ACM | 2025-02-05 | Paper |
| 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
Theoretical Computer Science | 2024-10-07 | Paper |
Minimum cut in \(O(m \log^2 n)\) time
Theory of Computing Systems | 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 |
scientific article; zbMATH DE number 7788468 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
| scientific article; zbMATH DE number 7788499 (Why is no real title available?) | 2024-01-15 | Paper |
Fully dynamic approximation of LIS in polylogarithmic time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
(available as arXiv preprint) | 2023-11-14 | Paper |
scientific article; zbMATH DE number 7765385 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-14 | Paper |
scientific article; zbMATH DE number 7765381 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-14 | Paper |
scientific article; zbMATH DE number 7724221 (Why is no real title available?)
(available as arXiv preprint) | 2023-08-08 | Paper |
Matching patterns with variables under edit distance
String Processing and Information Retrieval | 2023-08-04 | Paper |
On the hardness of computing the edit distance of shallow trees
String Processing and Information Retrieval | 2023-08-04 | Paper |
Better distance labeling for unweighted planar graphs
Algorithmica | 2023-06-05 | Paper |
Tight bound for the number of distinct palindromes in a tree
The Electronic Journal of Combinatorics | 2023-05-16 | Paper |
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
ACM Transactions on Algorithms | 2023-04-26 | Paper |
scientific article; zbMATH DE number 7650903 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
scientific article; zbMATH DE number 7651097 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
| On Indeterminate Strings Matching. | 2023-02-07 | Paper |
Existential length universality
(available as arXiv preprint) | 2023-02-07 | Paper |
| Top Tree Compression of Tries. | 2023-02-03 | Paper |
The Theory of Universal Graphs for Infinite Duration Games
Logical Methods in Computer Science | 2022-10-06 | Paper |
| Even faster elastic-degenerate string matching via fast matrix multiplication | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561710 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
| Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games | 2022-07-18 | Paper |
Streaming Dictionary Matching with Mismatches
(available as arXiv preprint) | 2022-07-18 | Paper |
scientific article; zbMATH DE number 7559139 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
| Quasi-Periodicity in Streams | 2022-07-18 | Paper |
| scientific article; zbMATH DE number 7559169 (Why is no real title available?) | 2022-07-18 | Paper |
Lower bounds for the number of repetitions in 2D strings
(available as arXiv preprint) | 2022-06-15 | Paper |
Elastic-Degenerate String Matching via Fast Matrix Multiplication
SIAM Journal on Computing | 2022-06-08 | Paper |
Fault-tolerant distance labeling for planar graphs
Theoretical Computer Science | 2022-05-10 | Paper |
| Incomplete directed perfect phylogeny in linear time | 2022-03-25 | Paper |
Strictly in-place algorithms for permuting and inverting permutations
(available as arXiv preprint) | 2022-03-25 | Paper |
| Better distance labeling for unweighted planar graphs | 2022-03-25 | Paper |
Streaming dictionary matching with mismatches
Algorithmica | 2022-03-22 | Paper |
Fast and longest rollercoasters
Algorithmica | 2022-03-22 | Paper |
Fault-tolerant distance labeling for planar graphs
Structural Information and Communication Complexity | 2022-03-22 | Paper |
Top tree compression of tries
Algorithmica | 2022-01-18 | Paper |
Top tree compression of tries
Algorithmica | 2022-01-18 | Paper |
| Edit distance with block operations | 2021-08-04 | Paper |
Near-optimal distance emulator for planar graphs
(available as arXiv preprint) | 2021-08-04 | Paper |
Fast entropy-bounded string dictionary look-up with mismatches
(available as arXiv preprint) | 2021-08-04 | Paper |
A faster construction of greedy consensus trees
(available as arXiv preprint) | 2021-07-28 | Paper |
Edit distance between unrooted trees in cubic time
(available as arXiv preprint) | 2021-07-28 | Paper |
Improved bounds for shortest paths in dense distance graphs
(available as arXiv preprint) | 2021-07-28 | Paper |
A faster FPTAS for \#Knapsack
(available as arXiv preprint) | 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
ACM Transactions on Algorithms | 2021-05-03 | Paper |
Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
SIAM Journal on Computing | 2021-04-14 | Paper |
Distinct squares in circular words
String Processing and Information Retrieval | 2021-02-16 | Paper |
Block trees
Journal of Computer and System Sciences | 2021-02-02 | Paper |
Tight upper and lower bounds on suffix tree breadth
Theoretical Computer Science | 2021-01-25 | Paper |
All non-trivial variants of 3-LDT are equivalent
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Slowing down top trees for better worst-case compression
(available as arXiv preprint) | 2020-12-16 | Paper |
Dispersion on trees
(available as arXiv preprint) | 2020-05-27 | Paper |
A family of approximation algorithms for the maximum duo-preservation string mapping problem
(available as arXiv preprint) | 2020-05-25 | Paper |
Universal reconstruction of a string
Theoretical Computer Science | 2020-02-20 | Paper |
Compressed range minimum queries
Theoretical Computer Science | 2020-02-20 | Paper |
Almost optimal distance oracles for planar graphs
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Computing quartet distance is equivalent to counting 4-cycles
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Tight tradeoffs for real-time approximation of longest palindromes in streams
Algorithmica | 2019-08-20 | Paper |
Hide and seek with repetitions
Journal of Computer and System Sciences | 2019-01-25 | Paper |
Longest gapped repeats and palindromes
Discrete Mathematics and Theoretical Computer Science. DMTCS | 2018-12-10 | 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
(available as arXiv preprint) | 2018-08-16 | Paper |
Speeding up dynamic programming in the line-constrained k-median
Theory of Computing Systems | 2018-08-03 | Paper |
Sparse suffix tree construction in optimal time and space
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| LZ77 factorisation of trees | 2018-04-19 | Paper |
| Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time | 2018-03-15 | Paper |
Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
(available as arXiv preprint) | 2018-03-15 | Paper |
| Better tradeoffs for exact distance oracles in planar graphs | 2018-03-15 | Paper |
Better tradeoffs for exact distance oracles in planar graphs
(available as arXiv preprint) | 2018-03-15 | Paper |
| Near-optimal compression for the planar graph metric | 2018-03-15 | Paper |
Near-optimal compression for the planar graph metric
(available as arXiv preprint) | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6850408 (Why is no real title available?) | 2018-03-15 | Paper |
scientific article; zbMATH DE number 6850408 (Why is no real title available?)
(available as arXiv preprint) | 2018-03-15 | Paper |
| Tree edit distance cannot be computed in strongly subcubic time (unless APSP can) | 2018-03-15 | Paper |
Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
(available as arXiv preprint) | 2018-03-15 | Paper |
| Labeling schemes for nearest common ancestors through minor-universal trees | 2018-03-15 | Paper |
Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
Theory of Computing Systems | 2018-03-01 | Paper |
The nearest colored node in a tree
Theoretical Computer Science | 2018-02-16 | Paper |
Efficiently finding all maximal -gapped repeats
(available as arXiv preprint) | 2018-01-24 | Paper |
Validating the Knuth-Morris-Pratt failure function, fast and online
Theory of Computing Systems | 2017-11-07 | Paper |
Randomized algorithms for finding a majority element
(available as arXiv preprint) | 2017-10-17 | Paper |
Faster longest common extension queries in strings over general alphabets
(available as arXiv preprint) | 2017-10-17 | Paper |
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
(available as arXiv preprint) | 2017-10-17 | Paper |
| The nearest colored node in a tree | 2017-10-17 | Paper |
Optimal distance labeling schemes for trees
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Wavelet trees meet suffix trees
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Brief announcement: Sublinear-space distance labeling using hubs
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
| Optimal pattern matching in LZW compressed strings | 2017-09-29 | Paper |
Optimal query time for encoding range majority
(available as arXiv preprint) | 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
Lecture Notes in Computer Science | 2016-09-29 | Paper |
Longest common extensions in trees
Theoretical Computer Science | 2016-06-16 | Paper |
Computing minimal and maximal suffixes of a substring
Theoretical Computer Science | 2016-06-16 | Paper |
Order-preserving pattern matching with \(k\) mismatches
Theoretical Computer Science | 2016-06-16 | Paper |
Approximating LZ77 via Small-Space Multiple-Pattern Matching
Algorithms - ESA 2015 | 2015-11-19 | Paper |
Universal reconstruction of a string
Lecture Notes in Computer Science | 2015-10-30 | Paper |
Optimal encodings for range top-\(k\), selection, and min-max
Automata, Languages, and Programming | 2015-10-27 | Paper |
Submatrix maximum queries in Monge matrices are equivalent to predecessor search
Automata, Languages, and Programming | 2015-10-27 | Paper |
| Computing the Longest Unbordered Substring | 2015-10-02 | Paper |
Longest -gapped repeat and palindrome
Fundamentals of Computation Theory | 2015-09-29 | Paper |
Strong inapproximability of the shortest reset word
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Euclidean TSP with few inner points in linear space
Algorithms and Computation | 2015-09-11 | Paper |
Longest common extensions in trees
Combinatorial Pattern Matching | 2015-08-20 | Paper |
Alphabet-dependent string searching with wexponential search trees
Combinatorial Pattern Matching | 2015-08-20 | Paper |
Encodings of range maximum-sum segment queries and applications
Combinatorial Pattern Matching | 2015-08-20 | Paper |
Approximate pattern matching in LZ77-compressed texts
Journal of Discrete Algorithms | 2015-05-04 | Paper |
Optimal pattern matching in LZW compressed strings
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Weighted ancestors in suffix trees
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Improved submatrix maximum queries in Monge matrices
Automata, Languages, and Programming | 2014-07-01 | Paper |
Order-preserving pattern matching with \(k\) mismatches
Combinatorial Pattern Matching | 2014-06-30 | Paper |
Computing minimal and maximal suffixes of a substring revisited
Combinatorial Pattern Matching | 2014-06-30 | Paper |
Simple and efficient LZW-compressed multiple pattern matching
Journal of Discrete Algorithms | 2014-04-01 | Paper |
LZ77-based self-indexing with faster pattern matching
LATIN 2014: Theoretical Informatics | 2014-03-31 | Paper |
Beating \(O(nm)\) in approximate LZW-compressed pattern matching
Algorithms and Computation | 2014-01-14 | Paper |
Minimal Discriminating Words Problem Revisited
String Processing and Information Retrieval | 2013-10-29 | Paper |
Discovering hidden repetitions in words
Lecture Notes in Computer Science | 2013-08-05 | Paper |
Converting SLP to LZ78 in almost Linear Time
Combinatorial Pattern Matching | 2013-06-14 | Paper |
Alphabetic minimax trees in linear time
Computer Science – Theory and Applications | 2013-06-14 | Paper |
Minimax trees in linear time with applications
European Journal of Combinatorics | 2012-11-15 | Paper |
Tying up the loose ends in fully LZW-compressed pattern matching
(available as arXiv preprint) | 2012-08-23 | Paper |
Simple and efficient LZW-compressed multiple pattern matching
Combinatorial Pattern Matching | 2012-08-14 | Paper |
A faster grammar-based self-index
Language and Automata Theory and Applications | 2012-06-08 | Paper |
Faster approximate pattern matching in compressed repetitive texts
Algorithms and Computation | 2011-12-16 | Paper |
Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
Algorithms – ESA 2011 | 2011-09-16 | Paper |
On minimising automata with errors
Mathematical Foundations of Computer Science 2011 | 2011-08-17 | Paper |
Chrobak normal form revisited, with applications
Implementation and Application of Automata | 2011-07-29 | Paper |
Finding the growth rate of a regular or context-free language in polynomial time
International Journal of Foundations of Computer Science | 2010-09-06 | Paper |
Validating the Knuth-Morris-Pratt failure function, fast and online
Computer Science – Theory and Applications | 2010-06-22 | Paper |
Grammar-Based Compression in a Streaming Model
Language and Automata Theory and Applications | 2010-05-26 | Paper |
On the problem of freeness of multiplicative matrix semigroups
Theoretical Computer Science | 2010-03-09 | Paper |
Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
Journal of Discrete Algorithms | 2010-02-26 | Paper |
Minimax Trees in Linear Time with Applications
Lecture Notes in Computer Science | 2009-12-11 | Paper |
Hyper-minimisation Made Efficient
Mathematical Foundations of Computer Science 2009 | 2009-10-16 | Paper |
2-Synchronizing Words
Language and Automata Theory and Applications | 2008-11-20 | Paper |
Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
Developments in Language Theory | 2008-10-30 | Paper |
A Combinatorial Approach to Collapsing Words
Lecture Notes in Computer Science | 2007-09-05 | Paper |
Optimal Bounds for Distinct Quartics
(available as arXiv preprint) | N/A | Paper |
