Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs(Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• A tree 3-spanner T of a graph G is a spanning tree of G such that the distance between any two vertices in T is at most 3 times of their distance in G. Madanlal et al have presented an O(n + m) time algorithm for finding a tree 3-spanner of a permutation graph. However, the complexity of their algorithm is not optimal, and their algorithm can not be easily parallelized. In this paper, we will propose an improved algorithm to solve the same problem in O (n) time. Moreover, our algorithm can be easily parallelized so that a tree 3-spanner of a permutation graph can be found in O (log n) time with O (n/(log n)) processors on the EREW PRAM computational model.

• 社団法人電子情報通信学会の論文
• 2003-11-01

著者

• Chen H‐c

  Department Of Information Management National Chin-yi Institute Of Technology Taichung

• Yang Chang-biau

  Department Of Computer Science And Engineering National Sun Yat-sen University

• CHEN Hon-Chan

  Department of Information Management, National Chin-Yi Institute of Technology

• WU Shin-Huei

  Department of Computer Science and Engineering, National Sun Yat-sen University

• Wu Shin-huei

  Department Of Computer Science And Engineering National Sun Yat-sen University

関連論文

• A Fast Initialization Algorithm for Single-Hop Wireless Networks(Network)
• Near-Optimal Block Alignments
• Generalization of Sorting in Single Hop Wireless Networks(Computation and Computational Models)
• Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs(Algorithms)
• Efficient Algorithms for Finding a Tree 3-Spanner on Permutation Graphs

スポンサーリンク