Tata Institute of Fundamental Research
Finding Optimal Shortest Path Trees
STCS Student Seminar
Speaker:
Kshitij Gajjar
Organiser:
Aditya Nema
Date:
Friday, 14 Jun 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Kshitij Gajjar |
| Organiser: | Aditya Nema |
| Date: | Friday, 14 Jun 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.