Computation of a Minimum Average Distance Tree on Circular-arc Graphs

Biswanath Jana; Sukumar Mondal; Madhumangal Pal

The average distance of a finite graph G=(V,E) is the average of the distances over all unordered pairs of vertices. A minimum average distance spanning tree of G is a spanning tree of G with minimum average distance. Such a tree is sometimes referred to as a minimum routing cost spanning tree. In this paper, we present an efficient algorithm to compute a minimum average distance spanning tree on circular-arc graph in O(n^2)time, where n is the number of vertices of the graph.

Select Volume / Issues:

• Volume 6,Issue 3, May 2015

Year:

2015

Type of Publication:

Article

Keywords:

Algorithms With Complexity; Circular-Arc Graphs; MAD Tree; Spanning Tree

Journal:

IJECCE

Volume:

6

Number:

3

Pages:

384-390

Month:

May