3 papers
cs.DS2024
Log Diameter Rounds MST Verification and Sensitivity in MPC
Sam Coy, Artur Czumaj, Gopinath Mishra +1
We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the se…
cs.DS2024
Modeling Online Paging in Multi-Core Systems
Mathieu Mari, Anish Mukherjee, Runtian Ren +1
Web requests are growing exponentially since the 90s due to the rapid development of the Internet. This process was further accelerated by the introduction of cloud services. It ha…
cs.DS2023
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one strin…