Additive tree 2-spanners of permutation graphs

文化大學機構典藏 CCUR > 商學院 > 資訊管理學系暨資訊管理研究所 > 期刊論文 > Item 987654321/21014

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: 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中所有的数据项都受到原著作权保护.