2 citations · 4 across the 4 of their papers we have counts for
5 papers
Girth Approximations in the CONGEST Model
Shiri Chechik, Gur Lifshitz, Doron Mukhtar
This paper advances the state of the art in girth approximation within the CONGEST model. Manoharan and Ramachandran [PODC '24] provided the first significant improvement in girth…
Testing Spreading Behavior in Networks with Arbitrary Topologies
Augusto Modanese, Yuichi Yoshida
Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologi…
Streaming Edge Coloring with Subquadratic Palette Size
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an -node graph arrive in an arbitrary order…
Reachability and Shortest Paths in the Broadcast CONGEST Model
Shiri Chechik, Doron Mukhtar
In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CON…
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
Shiri Chechik, Doron Mukhtar
In this paper, we consider distributed coloring for planar graphs with a small number of colors. We present an optimal (up to a constant factor) time algorithm for 6-c…