Dipan Dey

works on

approximation algorithms 1 congest model 1 lower bounds 1 minimum weight cycle 1 round complexity 1

From the 1 of 5 linked papers with an AI index.

collaborators

5 papers

cs.DC2026

The Complexity of Distributed Minimum Weight Cycle Approximation

Yi-Jun Chang, Yanyu Chen, Dipan Dey +4

The paper presents randomized approximation algorithms for the Minimum Weight Cycle problem in the CONGEST model, achieving a trade‑off between approximation ratio and round comple…

cs.DS2026

Low-Cost Arborescence Under Edge Faults

Dipan Dey, Telikepalli Kavitha

Our input is a directed graph $G = (V, E)$ on $n$ vertices and $m$ edges with a designated root vertex $r$ and a function $cos t : E \to R_{\geq 0}$ . The problem is t…

cs.DS2026

Nearly Optimal Fault Tolerant Distance Oracle

Dipan Dey, Manoj Gupta

We present an $f$ -fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from $[1 \dots W]$ . Given a set $F$ of $f$ edges, as well a…

cs.DS2025

Fault-Tolerant Approximate Distance Oracles with a Source Set

Dipan Dey, Telikepalli Kavitha

Our input is an undirected weighted graph $G = (V, E)$ on $n$ vertices along with a source set $S \subseteq V$ . The problem is to preprocess $G$ and build a compact data structure su…

cs.DS2025

Optimal Distributed Replacement Paths

Yi-Jun Chang, Yanyu Chen, Dipan Dey +3

We study the replacement paths problem in the $CONGEST$ model of distributed computing. Given an $s$ - $t$ shortest path $P$ , the goal is to compute, for every edge $e$ in $…