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.
| 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.