A distributed network is modeled by a graph having n nodes (processors) and diameter D.
We study the time complexity of approximating weighted (undirected) shortest paths on …

We present a deterministic (1+ o (1))-approximation O (n 1/2+ o (1)+ D 1+ o (1))-time
algorithm for solving the single-source shortest paths problem on distributed weighted …

We present a novel approach to graph partitioning based on the notion of cuts. Our
algorithm, called PUNCH, has two phases. The first phase performs a series of minimum-cut …

We present the first sublinear-time algorithm that can compute the edge connectivity λ of a
network exactly on distributed message-passing networks (the CONGEST model), as long …

Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we
give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ …

Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While
the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was …

We study the problem of computing the minimum cut in a weighted distributed message-
passing networks (the CONGEST model). Let λ be the minimum cut, n be the number of …

We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST
model). The goal is for every node in the (weighted) network to know the distance from every …

We revisit classical connectivity problems in the CONGEST model of distributed computing.
By using techniques from fault tolerant network design, we show improved constructions …

We revisit the classic broadcast problem, wherein we have k messages, each composed of
O (log n) bits, distributed arbitrarily across a network. The objective is to broadcast these …