School of Technology and Computer Science Seminars
Finding Optimal Shortest Path Trees
by Kshitij Gajjar (STCS, TIFR)
Friday, June 14, 2019
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
Abstract: Given a graph $G$ with one source vertex $s$ and several target vertices, a shortest path tree rooted at $s$ is a subgraph of $G$ that preserves distances from $s$ to each of the target vertices. A shortest path tree is called optimal if it has the minimum number of branching vertices (vertices of degree three or more). In this talk, we will see proofs of the following results. 1. Finding an optimal shortest path tree is $\mathsf{NP}$-hard for general graphs. 2. Finding an optimal shortest path tree is in $\mathsf{P}$ for interval graphs. This is based on joint work with Jaikumar. A condensed version of this talk will be given at CSR 2019 in Novosibirsk, Russia. |
Organised by | Aditya Nema |