7 papers
Low-Cost Arborescence Under Edge Faults
Dipan Dey, Telikepalli Kavitha
Our input is a directed graph on vertices and edges with a designated root vertex and a function . The problem is t…
The Complexity of Distributed Minimum Weight Cycle Approximation
Yi-Jun Chang, Yanyu Chen, Dipan Dey +4
We study the Minimum Weight Cycle (MWC) problem in the model of distributed computing. For undirected weighted graphs, we give a randomized -approximation…
Fault-Tolerant Approximate Distance Oracles with a Source Set
Dipan Dey, Telikepalli Kavitha
Our input is an undirected weighted graph on vertices along with a source set . The problem is to preprocess and build a compact data structure su…
Optimal Distributed Replacement Paths
Yi-Jun Chang, Yanyu Chen, Dipan Dey +3
We study the replacement paths problem in the model of distributed computing. Given an - shortest path , the goal is to compute, for every edge in $…
Near Optimal Dual Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta
We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set of two edges, as well as a source node and a destination node , our or…
Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta
We present an -fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from . Given a set of edges, as well a…
Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
Dipan Dey, Manoj Gupta
In a graph with a source , we design a distance oracle that can answer the following query: Query -- find the length of shortest path from a fixed source to any…