A linear time algorithm for constructing tree 4-spanner in 2-trees

被引：0

作者：

Panda, BS ^{[1
]}

Das, A ^{[1
]}

机构：

[1] Indian Inst Technol, Comp Sci & Applicat Grp, Dept Math, New Delhi 110016, India

来源：

INTELLIGENT INFORMATION TECHNOLOGY, PROCEEDINGS | 2004年 / 3356卷

关键词：

tree spanner; distance in graphs; graph algorithms; 2-trees;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. It has been shown in [3] that the problem of recognizing whether a graph admits a tree t-spanner is NP-complete for t greater than or equal to 4. In this paper, we present a linear time algorithm for constructing a tree 4-spanner in a tree 4-spanner admissible 2-tree.

引用

页码：21 / 30

页数：10