5 citations · 10 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Shiri Chechik, Tianyi Zhang
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph while edges are inserted and deleted from the graph. The first non-tr…
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem +1
In this paper we provide a time algorithm that computes a -multiplicative approximation of the girth of a -node -edge directed graph with non-negati…
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
Noga Alon, Shiri Chechik, Sarel Cohen
In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the random…