+91-674-249-4082

Submitted by admin on 15 October, 2014 - 20:23

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.

**School of Mathematical Sciences**

NISER, PO- Bhimpur-Padanpur, Via- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

Corporate Site - This is a contributing Drupal Theme

Design by WeebPal.

Design by WeebPal.