7 papers
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…
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…
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…
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 (…