14 citations · 19 across the 13 of their papers we have counts for
22 papers
Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications
Keerti Choudhary, Amit Kumar, Lakshay Saggi
Sensitivity oracles preprocess a graph so that queries can be answered after any edge insertions and deletions, without recomputing from scratch. For structural optimization pr…
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 …
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)…
Fault-Tolerant Bounded Flow Preservers
Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa +1
Given a directed graph with vertices, edges and a designated source vertex , we consider the question of finding a sparse subgraph of that pres…
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…
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +4
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertice…
Fault-Tolerant ST-Diameter Oracles
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
Given two vertex sets and in a graph, the -diameter is the maximum --distance between vertices and . We study the problem of estimating the $ST…
Compact Distance Oracles with Large Sensitivity and Low Stretch
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses an input graph . When queried with the triple $(s,t,F…
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…
Fixed-Parameter Sensitivity Oracles
Davide Bilò, Katrin Casel, Keerti Choudhary +5
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f…
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…
Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
The classical problem of degree sequence realizability asks whether or not a given sequence of positive integers is equal to the degree sequence of some -vertex undirected s…
Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances
Keerti Choudhary, Omer Gold
The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread thr…
An efficient strongly connected components algorithm in the fault tolerant model
Surender Baswana, Keerti Choudhary, Liam Roditty
In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V…
Dynamic DFS Tree in Undirected Graphs: breaking the barrier
Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary +1
Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes time to build a DFS tree for a given u…
A Note on Integer Domination of Cartesian Product Graphs
K. Choudhary, S. Margulies, I. V. Hicks
Given a graph , a dominating set is a set of vertices such that any vertex in has at least one neighbor (or possibly itself) in . A -dominating multiset is…
A Note on Total and Paired Domination of Cartesian Product Graphs
K. Choudhary, S. Margulies, I. V. Hicks
A dominating set for a graph is a subset of such that any vertex not in has at least one neighbor in . The domination number is the size of a minimum d…