3 citations · 6 across the 15 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024★ 2 cited
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string from left to right into blocks (called phrases) so that each ph…
cs.DS2024
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
Paweł Gawrychowski, Egor Gorbachev, Tomasz Kociumaka
Min-plus matrix multiplication is used in many problems operating on distances in graphs or solvable by dynamic programming. Assuming the APSP hypothesis, there is no subcubic-time…
cs.DS2024
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev, Tomasz Kociumaka
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines…