# News & Events

## Seminar

Date/Time:
Monday, October 20, 2014 - 11:35 to 12:35
Venue:
LH-101
Speaker:
Rajula Srivastava
Affiliation:
NISER, Bhubaneswar
Title:
Tree t spanners in 2 connected outerplanar graph

Abstract: The problem of finding sparse underlying subgraphs, which also maintain the distance information between any 2 pair of vertices, is an important one in graph theory, with several applications. One approach would be to find tree $t$-spanners, i.e., spanning trees in which the distance between any pair of vertices is atmost $t$ times their distance in the original graph $(t>=1)$. The tree $t$ spanner problem has been shown to be NP-complete, when $t$ is part of the input, for general graphs. In this talk, we will study an algorithm which solves the tree $t$ spanner problem in 2-connected outerplanar graphs, in $O(n)$ time ($n$ is the number of vertices).

A familiarity with the basic concepts of graph theory is desirable.