We give an algorithm for computing exact maximum flows on graphs with edges and integer
capacities in the range in time. We use to suppress logarithmic factors in. For sparse graphs …

We provide universally-optimal distributed graph algorithms for (1+∊)-approximate shortest
path problems including shortest-path-tree and transshipment. The universal optimality 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) …

A seminal work of Ahn-Guha-McGregor, PODS'12 showed that one can compute a cut
sparsifier of an unweighted undirected graph by taking a near-linear number of linear …

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up
to polylogarithmic factors in five models of computation: the two-party communication, AND …

In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested
Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic …

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero
row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear …

Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used
in machine learning over graphs. As real-world networks are becoming very large and …

This paper presents parallel, distributed, and quantum algorithms for single-source shortest
paths when edges can have negative integer weights (negative-weight SSSP). We show a …

In this paper, we bring the techniques of the Laplacian paradigm to the congested clique,
while further restricting ourselves to deterministic algorithms. In particular, we show how to …