5 papers
Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg +3
Given an undirected weighted graph , a -approximate low-stretch spanning tree (LSST) is a tree that approximates the distance metric of up to a -factor…
A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg +1
The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min…
A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
Nick Fischer, Bernhard Haeupler, Rustam Latypov +2
We give the first parallel algorithm with optimal work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edg…
Critical probabilities for positively associated, finite-range dependent percolation models
Laurin Köhler-Schindler, Aurelio L. Sulser
On a locally finite, infinite tree , let denote the critical probability for Bernoulli percolation. We prove that every positively associated, finite-range dependent pe…
Near-Optimal Algorithm for Directed Expander Decompositions
Aurelio L. Sulser, Maximilian Probst Gutenberg
In this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m). Further, our algorithm can maintain such a…