10 papers
-Depth Parallel Reachability Faster than Transitive Closure
Shimon Kogan, Merav Parter
A -shortcut of a directed graph is a subset of edges drawn from the transitive closure whose addition reduces the graph diameter to at most . In the special…
Space-Optimal Sensitivity Oracles for Single-Source Mincuts
Koustav Bhanja, Merav Parter, Asaf Petruschka
We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to source change…
Multi-Source Reachability in Near-Optimal Time
Shimon Kogan, Merav Parter
The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For -vertex digraphs and a subset of sources $S \subse…
Color Fault-Tolerant Distance Preservers: Ãptimal Size in Conditionally Ãptimal Time
Merav Parter, Asaf Petruschka
We revisit the problem of fault-tolerant (FT) distance preservers, when failure events in the network admit a form of correlation modeled as color faults. FT distance preservers ar…
New Oracles and Labeling Schemes for Vertex Cut Queries
Yonggang Jiang, Merav Parter, Asaf Petruschka
We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected -vertex graph and integer parameter , t…
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
Julia Chuzhoy, Merav Parter
A -spanner of an undirected -vertex graph is a sparse subgraph of that preserves all pairwise distances between its vertices to within multiplicative factor ,…