All reports by Author Kshitij Gajjar:

__
TR18-211
| 3rd December 2018
__

Kshitij Gajjar, Jaikumar Radhakrishnan#### 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 with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>