Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Undirected Replacement Paths: Dual Fault Reduces to Single Source
Jakob Nogler, Virginia Vassilevska Williams
Given a graph and two fixed vertices and , the Replacement Path Problem (RP) is to compute for every edge , the distance between and when is removed. There ar…
cs.DS2022
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
Ce Jin, Jakob Nogler
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS…