Kshitij Gajjar

activity

20172026

most citedDistance-preserving Subgraphs of Interval Graphs

2 citations · 4 across the 11 of their papers we have counts for

collaborators

Showing 2018Show all

2 papers · 1 filter

cs.CC2018

Parametric Shortest Paths in Planar Graphs

Kshitij Gajjar, Jaikumar Radhakrishnan

We construct a family of planar graphs ${G_{n}}_{n \geq 4}$ , where $G_{n}$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$ , and edge weights that change linearly…

cs.DS2018

Minimizing Branching Vertices in Distance-preserving Subgraphs

Kshitij Gajjar, Jaikumar Radhakrishnan

It is $NP$ -hard to determine the minimum number of branching vertices needed in a single-source distance-preserving subgraph of an undirected graph. We show that this prob…