5 citations · 10 across the 6 of their papers we have counts for
9 papers · 1 filter
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
Shiri Chechik, Ofer Magen
In the Single Source Replacement Paths (SSRP) problem we are given a graph , and a shortest paths tree rooted at a node , and the goal is to output for…
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…
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…