20 citations · 76 across the 29 of their papers we have counts for
4 papers · 1 filter
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph , a near-optimal -expander decomposition is…
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Optimal Electrical Oblivious Routing on Expanders
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an -edge graph that is a -expander, i.e.…
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…