Speaker: |
Kshitij Gajjar |

Date: |
Saturday, 9 Jan 2016, 10:00 to 11:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

In this work, we explore interval graphs. Given an interval graph $G$ on $k$ terminals, we describe a method of producing a distance preserving minor of $G$ having at most $k^2$ vertices. Thus, $f(k,\mathcal{I})\le k^2$, where $\mathcal{I}$ is the family of all interval graphs. We also show that there are interval graphs on which our method does not perform optimally. In particular, there exists an interval graph which admits a distance preserving minor of size $O(k\log k)$, but our method produces a distance preserving minor of size $\Omega(k^2)$ for it. Thus, the problem of finding an optimal distance preserving minor for interval graphs remains open.