Showing 2024 · cs.DSShow all
3 papers · 2 filters
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
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Karl Bringmann, Egor Gorbachev
In an -edge host graph , all triangles can be listed in time [Itai, Rodeh '78], and all -cycles can be listed in time whe…
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…