9 papers
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of…
Pairwise Reachability Oracles and Preservers under Failures
Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary
In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let be a directed graph on -no…
Budgeted Dominating Sets in Uncertain Graphs
Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy +2
We study the {\em Budgeted Dominating Set} (BDS) problem on uncertain graphs, namely, graphs with a probability distribution associated with the edges, such that an edge ex…
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
Diptarka Chakraborty, Keerti Choudhary
In this paper, we consider the question of computing sparse subgraphs for any input directed graph on vertices and edges, that preserves reachability and/or stron…
Distributed Graph Realizations
John Augustine, Keerti Choudhary, Avi Cohen +3
We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for repr…
Efficiently Realizing Interval Sequences
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
We consider the problem of realizable interval-sequences. An interval sequence comprises of integer intervals such that , and is said t…