News & Events


Monday, October 20, 2014 - 11:35 to 12:35
Rajula Srivastava
NISER, Bhubaneswar
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.

Contact us

School of Mathematical Sciences

NISERPO- Bhimpur-PadanpurVia- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

Corporate Site - This is a contributing Drupal Theme
Design by WeebPal.