Oren Weimann

collaborators

6 papers

cs.DC2026

$O ~$ 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…

cs.DS2026

A Tight Bound for Facial Distance Patterns in Planar Graphs

Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann

Let $G$ be an undirected unweighted planar graph and let $S = (s_{0}, \dots, s_{k - 1})$ be the vertices of a designated face, listed in cyclic order. Consider a vector that stores the dis…

cs.DC2026

A Simple Distributed Deterministic Planar Separator

Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann

A balanced separator of a graph $G$ is a set of vertices whose removal disconnects the graph into connected components that are a constant factor smaller than $G$ . Lipton and Tarja…

cs.DC2025

Distributed Maximum Flow in Planar Graphs

Yaseen Abd-Elhaleem, Michal Dory, Merav Parter +1

The dual of a planar graph $G$ is a planar graph $G^{*}$ that has a vertex for each face of $G$ and an edge for each pair of adjacent faces of $G$ . The profound relationship between…

cs.DS2025

Ãptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs

Itai Boneh, Shiri Chechik, Shay Golan +2

We present a labeling scheme that assigns labels of size $O ~ (1)$ to the vertices of a directed weighted planar graph $G$ , such that for any fixed $ε > 0$ from the lab…

cs.DS2025

Faster Construction of a Planar Distance Oracle with Ã(1) Query Time

Itai Boneh, Shay Golan, Shay Mozes +2

We show how to preprocess a weighted undirected $n$ -vertex planar graph in $O ~ (n^{4/3})$ time, such that the distance between any pair of vertices can then be reported in $\t…