10 citations · 12 across the 10 of their papers we have counts for
13 papers · 1 filter
Near-Optimal Replacement Path Coverings
Davide Bilò, Keerti Choudhary, Sarel Cohen +1
Let and be positive integers. An -replacement path covering (RPC) for a graph is a family of subgraphs such that, for every set of at most …
Simpler and Improved Replacement Path Coverings
Davide Bilò, Shiri Chechik, Keerti Choudhary +2
An important tool in the design of fault-tolerant graph data structures are -replacement path coverings (RPCs). An RPC is a family of subgraphs of a given grap…
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We design sensitivity oracles for error-prone networks. For a network problem , the data structure preprocesses a network and sensitivity parameter such that, for…
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
A distance oracle (DO) with stretch for a graph is a data structure that, when queried with vertices and , returns a value such that $d(s,t)…
A New Approach for Approximating Directed Rooted Networks
Sarel Cohen, Lior Kamma, Aikaterini Niklanovits
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph , where , and an integer , the goal i…
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners wi…