7 papers · 1 filter
Almost Optimal Multiple Source Shortest Paths and Reachability
Barna Saha, Yinzhan Xu, Christopher Ye
Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweig…
Deterministic Monotone Min-Plus Product and Convolution
Ce Jin, Jaewoo Park, Barna Saha +1
The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. In this problem, we are given two integer…
Hardness of Dynamic Tree Edit Distance and Friends
Bingbing Hu, Jakob Nogler, Barna Saha
String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substituti…
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha +1
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components,…
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu +1
Single Source Shortest Paths () is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain…