9 papers
DAG Projections: Reducing Distance and Flow Problems to DAGs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We show that every directed graph with vertices and edges admits a directed acyclic graph (DAG) with edges, called a DAG projection, that can either $(1+1/…
The Complexity of Distributed Minimum Weight Cycle Approximation
Yi-Jun Chang, Yanyu Chen, Dipan Dey +4
We study the Minimum Weight Cycle (MWC) problem in the model of distributed computing. For undirected weighted graphs, we give a randomized -approximation…
Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak +1
We give almost-linear-time algorithms for approximating rooted minimum cut and maximum arborescence packing in directed graphs, two problems that are dual to each other [Edm73]. Mo…
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph with …
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and vert…
Reducing Shortcut and Hopset Constructions to Shallow Graphs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specific…
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay +1
We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweigh…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…