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)

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.