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 …

We devise new algorithms for the single-source shortest paths (SSSP) problem with non-
negative edge weights in the CONGEST model of distributed computing. While close-to …

In the distributed all-pairs shortest paths problem (APSP), every node in the weighted
undirected distributed network (the CONGEST model) needs to know the distance from …

We describe approximation algorithms in Linial's classic LOCAL model of distributed
computing to find maximum-weight matchings in a hypergraph of rank r. Our main result is a …

The maximum weighted matching (mwm) problem is one of the most well-studied
combinatorial optimization problems in distributed graph algorithms. Despite a long …

In the coordinator model of communication with s servers, given an arbitrary non-negative
function f, we study the problem of approximating the sum∑ i∈[n] f (xi) up to a 1±ε factor …

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 …

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 …

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 …

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first
algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to …