1 citations · 1 across the 7 of their papers we have counts for
13 papers
An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions
Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka
Given an undirected weighted graph on vertices, the classical Gomory-Hu tree of is a structure that encodes an arbitrary minimum -cut for every us…
Fast Metric Decompositions in High Dimension
Robert Krauthgamer, Asaf Petruschka, Nir Petruschka
Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of -…
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…
Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
Koustav Bhanja, Asaf Petruschka
We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any (or less) vertex failures occur. An -FT Ste…
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…
Fault-Equivalent Lowest Common Ancestors
Asaf Petruschka
Let be a rooted tree in which a set of vertices are marked. The lowest common ancestor (LCA) of is the unique vertex with the following property: after failing (…
Parks and Recreation: Color Fault-Tolerant Spanners Made Local
Merav Parter, Asaf Petruschka, Shay Sapir +1
We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to failures of entire color classes. The failure of even a…
Connectivity Labeling in Faulty Colored Graphs
Asaf Petruschka, Shay Sapir, Elad Tzalik
Fault-tolerant connectivity labelings are schemes that, given an -vertex graph and , produce succinct yet informative labels for the elements of the graph. Gi…
Color Fault-Tolerant Spanners
Asaf Petruschka, Shay Sapir, Elad Tzalik
We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a co…
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, Seth Pettie
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An -vertex/edge fault tolerant (-V/EFT) co…
Near-Optimal Distributed Computation of Small Vertex Cuts
Merav Parter, Asaf Petruschka
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributed computing. Despite extensive research in this area, our understanding of the…
Õptimal Dual Vertex Failure Connectivity Labels
Merav Parter, Asaf Petruschka
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given -vertex graph , an -VFT (resp., EFT) connectivity l…