2 citations · 3 across the 4 of their papers we have counts for
5 papers
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…
Ramsey Spanning Trees and their Applications
Ittai Abraham, Shiri Chechik, Michael Elkin +2
The metric Ramsey problem asks for the largest subset of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion.…
Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering of data points is a fundamental tool in data analysis. We consider points in a relaxed metric space, where the triangle inequality holds within a constant factor. Th…
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especiall…
Secluded Connectivity Problems
Shiri Chechik, M. P. Johnson, Merav Parter +1
Consider a setting where possibly sensitive information sent over a path in a network is visible to every {neighbor} of the path, i.e., every neighbor of some node on the path, thu…