Distributed processing of large-scale graph data has many practical applications and has
been widely studied. In recent years, a lot of distributed graph processing frameworks and …

This paper presents significantly improved deterministic algorithms for some of the key
problems in the area of distributed graph algorithms, including network decomposition …

We present a universally-optimal distributed algorithm for the exact weighted min-cut. The
algorithm is guaranteed to complete in Õ (D+√ n) rounds on every graph, recovering the …

We give the first almost-linear time algorithms for several problems in incremental graphs
including cycle detection, strongly connected component maintenance, st shortest path …

This paper introduces stronger notions for approximate single-source shortest-path
distances and gives simple reductions to compute them from weaker standard notions of …

We present a parallel algorithm for the (1—ɛ)-approximate maximum flow problem in
capacitated, undirected graphs with n vertices and m edges, achieving O (ɛ-3 polylog n) …

This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its
running time and number of comparisons when combined with a sufficiently efficient heap …

This paper presents new deterministic and distributed low-diameter decomposition
algorithms for weighted graphs. In particular, we show that if one can efficiently compute …

We give the first almost-linear total time algorithm for deciding if a flow of cost at most F still
exists in a directed graph, with edge costs and capacities, undergoing decremental updates …

The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows
that to compute a Δ+ 1 coloring of the graph, where Δ denotes the maximum degree, it …