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 条
  • [1] A linear time algorithm for finding tree 3-spanner on 2-trees
    Panda, BS
    Das, SK
    FOUNDATIONS OF INFORMATION TECHNOLOGY IN THE ERA OF NETWORK AND MOBILE COMPUTING, 2002, 96 : 292 - 309
  • [2] A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
    Barman, Sambhu Charan
    Mondal, Sukumar
    Pal, Madhumangal
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (04) : 743 - 755
  • [3] A linear time algorithm for finding tree 3-spanner on 2 trees
    Department of Mathematics, Indian Institute of Technology, Delhi, Hauz Khas, New Delhi 110 016, India
    不详
    IFIP Advances in Information and Communication Technology, 2002, 96 : 292 - 309
  • [4] A Linear Time Algorithm for Computing Longest Paths in 2-Trees
    Markov, Minko
    Vassilev, Tzvetalin S.
    Manev, Krassimir
    ARS COMBINATORIA, 2013, 112 : 329 - 351
  • [5] A linear time algorithm for constructing tree 3-spanner in simple chordal bipartite graphs
    Das, Anita
    Panda, B. S.
    Lal, Rajendra P.
    ICIT 2006: 9TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY, PROCEEDINGS, 2006, : 301 - +
  • [6] TREE POLYTOPE ON 2-TREES
    MARGOT, F
    PRODON, A
    LIEBLING, TM
    MATHEMATICAL PROGRAMMING, 1994, 63 (02) : 183 - 191
  • [7] GENERATION OF TREES, COTREES AND 2-TREES OF A LINEAR GRAPH
    CAHIT, R
    CAHIT, I
    PROCEEDINGS OF THE INSTITUTION OF ELECTRICAL ENGINEERS-LONDON, 1972, 119 (09): : 1275 - &
  • [8] Resistance distance in straight linear 2-trees
    Barrett, Wayne
    Evans, Emily J.
    Francis, Amanda E.
    DISCRETE APPLIED MATHEMATICS, 2019, 258 : 13 - 34
  • [9] On some relations between 2-trees and tree metrics
    Leclerc, B
    Makarenkov, V
    DISCRETE MATHEMATICS, 1998, 192 (1-3) : 223 - 249
  • [10] Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
    La Doerr, Caro
    Ramakrishna, G.
    Schmidt, Jens M.
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2013, 2013, 8165 : 225 - 236
12345