Event calendar file
School of Technology and Computer Science Seminars
Parametric Shortest Paths in Directed Graphs
by Kshitij Gajjar (School of Technology and Computer Science, TIFR)
Friday, January 5, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
| Description |
Let $G$ be a directed graph on $n$ vertices (with two designated vertices $s$ and $t$) such that the edge weights of $G$ are real-valued linear functions of a parameter $\lambda$. Thus, as $\lambda$ varies from $0$ to $+\infty$, the edge weights of $G$ vary, and the shortest path from $s$ to $t$ may (or may not) vary. We ask the following question: as $\lambda$ takes on different real values from $0$ to $+\infty$, how many different shortest $s-t$ paths can $G$ have?
In this talk, we will prove that the number of different shortest $s-t$ paths can be at most $n^{O(\log n)}$. We will also examine a graph which has $n^{\Omega(\log n)}$ different shortest $s-t$ paths.
|
