| 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
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?)
| 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788499 (Why is no real title available?)
| 2024-01-15 | Paper |
scientific article; zbMATH DE number 7765385 (Why is no real title available?)
| 2023-11-14 | 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 |
scientific article; zbMATH DE number 7765381 (Why is no real title available?)
| 2023-11-14 | Paper |
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
| 2023-11-14 | Paper |
scientific article; zbMATH DE number 7724221 (Why is no real title available?)
| 2023-08-08 | Paper |
On the hardness of computing the edit distance of shallow trees
String Processing and Information Retrieval | 2023-08-04 | Paper |
Matching patterns with variables under edit distance
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 |
Existential length universality
| 2023-02-07 | Paper |
scientific article; zbMATH DE number 7650903 (Why is no real title available?)
| 2023-02-07 | Paper |
scientific article; zbMATH DE number 7651097 (Why is no real title available?)
| 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
Logical Methods in Computer Science | 2022-10-06 | Paper |
scientific article; zbMATH DE number 7561710 (Why is no real title available?)
| 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 |
scientific article; zbMATH DE number 7559169 (Why is no real title available?)
| 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 |
scientific article; zbMATH DE number 7559139 (Why is no real title available?)
| 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
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
| 2022-03-25 | Paper |
Better distance labeling for unweighted planar graphs
| 2022-03-25 | Paper |
Fault-tolerant distance labeling for planar graphs
Structural Information and Communication Complexity | 2022-03-22 | Paper |
Streaming dictionary matching with mismatches
Algorithmica | 2022-03-22 | Paper |
Fast and longest rollercoasters
Algorithmica | 2022-03-22 | 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
| 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
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
| 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 |
Compressed range minimum queries
Theoretical Computer Science | 2020-02-20 | Paper |
Universal reconstruction of a string
Theoretical Computer Science | 2020-02-20 | 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 |
Almost optimal distance oracles for planar graphs
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
| 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 |
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 |
scientific article; zbMATH DE number 6850408 (Why is no real title available?)
| 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
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 \(\alpha\)-gapped repeats
| 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
| 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
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
| 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 |
Submatrix maximum queries in Monge matrices are equivalent to predecessor search
Automata, Languages, and Programming | 2015-10-27 | Paper |
Optimal encodings for range top-\(k\), selection, and min-max
Automata, Languages, and Programming | 2015-10-27 | Paper |
Computing the Longest Unbordered Substring
| 2015-10-02 | Paper |
Longest \(\alpha \)-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 |
Encodings of range maximum-sum segment queries and applications
Combinatorial Pattern Matching | 2015-08-20 | 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 |
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 |
Computing minimal and maximal suffixes of a substring revisited
Combinatorial Pattern Matching | 2014-06-30 | Paper |
Order-preserving pattern matching with \(k\) mismatches
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
| 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
| N/A | Paper |
