by
Kshitij Gajjar(School of Technology and Computer Science, TIFR)
→
Asia/Kolkata
A-201 (STCS Seminar Room)
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.
