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
相关论文
共 50 条
  • [21] A polynomial time algorithm for constructing the refined Buneman tree
    Bryant, D
    Moulton, V
    APPLIED MATHEMATICS LETTERS, 1999, 12 (02) : 51 - 56
  • [22] A Linear Time Algorithm for Embedding Christmas Trees into Certain Trees
    Rajasingh, Indra
    Rajan, R. Sundara
    Manuel, Paul
    PARALLEL PROCESSING LETTERS, 2015, 25 (04)
  • [23] A Linear Time Algorithm for L(2,1)-Labeling of Trees
    Hasunuma, Toru
    Ishii, Toshimasa
    Ono, Hirotaka
    Uno, Yushi
    ALGORITHMS - ESA 2009, PROCEEDINGS, 2009, 5757 : 35 - +
  • [24] A Linear Time Algorithm for Rolling Binary Trees
    Tanev, George
    Bozinovski, Adrijan
    17TH IEEE INTERNATIONAL CONFERENCE ON SMART TECHNOLOGIES - IEEE EUROCON 2017 CONFERENCE PROCEEDINGS, 2017, : 255 - 260
  • [25] A LINEAR TIME ALGORITHM FOR FULL STEINER TREES
    HWANG, FK
    OPERATIONS RESEARCH LETTERS, 1986, 4 (05) : 235 - 237
  • [26] A linear-time algorithm for the generation of trees
    Alonso, L
    Remy, JL
    Schott, R
    ALGORITHMICA, 1997, 17 (02) : 162 - 182
  • [27] A linear-time algorithm for the generation of trees
    L. Alonso
    J. L. Rémy
    R. Schott
    Algorithmica, 1997, 17 : 162 - 182
  • [28] A Linear Time Algorithm for L(2,1)-Labeling of Trees
    Toru Hasunuma
    Toshimasa Ishii
    Hirotaka Ono
    Yushi Uno
    Algorithmica, 2013, 66 : 654 - 681
  • [29] A Linear Time Algorithm for L(2,1)-Labeling of Trees
    Hasunuma, Toru
    Ishii, Toshimasa
    Ono, Hirotaka
    Uno, Yushi
    ALGORITHMICA, 2013, 66 (03) : 654 - 681
  • [30] A linear time algorithm for balance vertices on trees
    Van Huy Pham
    Kien Trung Nguyen
    Tran Thu Le
    DISCRETE OPTIMIZATION, 2019, 32 : 37 - 42
12345