From the 1 of 6 linked papers with an AI index.
6 papers
Cut Query Reachability for DAGs with Subquadratic Queries
Ben Bals, Matei Tinca, Yasamin Nazari
The paper presents a deterministic algorithm for single-source reachability in directed acyclic graphs using subquadratic cut queries, achieving O(n √(n log n)) query complexity an…
Faster Randomized and Deterministic k-Clustering on Graphs
Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. +1
In this paper, we study the -clustering and -center problems on graphs, where -clustering generalizes the -median () and -means () problems. We obt…
Revisiting Diameter in Directed Graphs
Ben Bals, Joakim Blikstad, Daniel Dadush +2
The reachability diameter () of a directed graph is the maximum distance over all pairs where is reachable from . This notion is present in the def…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Approximation Algorithms for Optimal Hopsets
Michael Dinitz, Ama Koranteng, Yasamin Nazari
For a given graph , a "hopset" with hopbound and stretch is a set of edges such that between every pair of vertices and , there is a path with at most …
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yasamin Nazari +1
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with edges and nodes unde…