資料載入中.....
|
請使用永久網址來引用或連結此文件:
https://irlib.pccu.edu.tw/handle/987654321/21014
|
| 題名: | Additive tree 2-spanners of permutation graphs |
| 作者: | Wang, FH (Wang, Fu-Hsing)
Chen, HC (Chen, Hon-Chan) |
| 貢獻者: | 資訊管理研究所 |
| 關鍵詞: | spanner
permutation graph
algorithm |
| 日期: | 2009 |
| 上傳時間: | 2011-12-12 14:09:25 (UTC+8) |
| 摘要: | Let G be a connected graph. A spanning tree T of G is a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. If their distances in T and G differ by at most t, then T is an additive tree t-spanner of G. In this paper, we show that any permutation graph has an additive tree 2-spanner, and it can be found in O(n) time sequentially or in O(log n) time with O(n/log n) processors on the EREW PRAM computational model by using a previously published algorithm for finding a tree 3-spanner of a permutation graph. |
| 顯示於類別: | [資訊管理學系暨資訊管理研究所 ] 期刊論文
|
在CCUR中所有的資料項目都受到原著作權保護.
|
