Asaf Petruschka

collaborators

5 papers

cs.DS2025

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 $f$ (or less) vertex failures occur. An $f$ -FT Ste…

cs.DS2025

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…

cs.DS2025

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 $n$ -vertex graph $G = (V, E)$ and integer parameter $f \geq 1$ , t…

cs.DS2024

Fault-Equivalent Lowest Common Ancestors

Asaf Petruschka

Let $T$ be a rooted tree in which a set $M$ of vertices are marked. The lowest common ancestor (LCA) of $M$ is the unique vertex $ℓ$ with the following property: after failing (…

cs.DS2024

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 $f$ failures of entire color classes. The failure of even a…