5 citations · 9 across the 4 of their papers we have counts for
4 papers
Better Online Deterministic Packet Routing on Grids
Guy Even, Moti Medina, Boaz Patt-Shamir
We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link…
Fast Partial Distance Estimation and Applications
Christoph Lenzen, Boaz Patt-Shamir
We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. A deterministic…
Improved Distributed Steiner Forest Construction
Christoph Lenzen, Boaz Patt-Shamir
We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant , a -approximati…
Distributed Discovery of Large Near-Cliques
Zvika Brakerski, Boaz Patt-Shamir
Given an undirected graph and , a set of nodes is called -near clique if all but an fraction of the pairs of nodes in the set have a link between them. In this pa…