3 papers
cs.DS2025
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…
cs.DS2024
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…
math.PR2024
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…