6 papers
ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs
Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann
Persistent efforts in recent years have been devoted to devising distributed algorithms for fundamental optimization problems in planar graphs. In particular, for Single-Source Sho…
Deterministic Distance Approximation in MPC via Improved Hitting Sets
Kyungjin Cho, Michal Dory, Yannic Maus +1
In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we si…
A Simple Distributed Deterministic Planar Separator
Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann
A balanced separator of a graph is a set of vertices whose removal disconnects the graph into connected components that are a constant factor smaller than . Lipton and Tarja…
Improved All-Pairs Approximate Shortest Paths in Congested Clique
Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang +2
In this paper, we present a new randomized -approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $O(\log \l…
Distributed Maximum Flow in Planar Graphs
Yaseen Abd-Elhaleem, Michal Dory, Merav Parter +1
The dual of a planar graph is a planar graph that has a vertex for each face of and an edge for each pair of adjacent faces of . The profound relationship between…
Massively Parallel Algorithms for Approximate Shortest Paths
Michal Dory, Shaked Matar
We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take rounds…