Tata Institute of Fundamental Research

Distance Preserving Minors in Graphs

Project Seminar
Speaker: Kshitij Gajjar
Organiser: Kavitha Telikepalli
Date: Tuesday, 20 Jan 2015, 16:00 to 17:30
Venue: D-405 (D-Block Seminar Room)

(Scan to add to calendar)
Abstract:  Abstract: We consider undirected, connected graphs with nonnegative weights on the edges. Additionally, a special subset of vertices called terminals is provided as input. A graph H is said to be a distance preserving minor of G if: (i) H is a minor of G, and (ii) the distance between each pair of terminals is exactly the same in G and H. Note that the edge weights can be reassigned in H (as long as they are nonnegative). Given a family of graphs F, let f(k,F) be the minimum integer such that every graph in F with k terminals admits a distance preserving minor with at most f(k,F) vertices. We will see results for the best known bounds on the value of f for different families of graphs, namely trees, planar graphs and interval graphs.