An efficient parallel strategy for computing K-terminal reliability and finding most vital edges in 2-trees and partial 2-trees

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 期刊論文 > Item 987654321/29165

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/29165

题名:	An efficient parallel strategy for computing K-terminal reliability and finding most vital edges in 2-trees and partial 2-trees
作者:	Ho,CW;Hsieh,SY;Chen,GH
贡献者:	資訊工程研究所
关键词:	STEINER TREES;NETWORKS;GRAPHS;COMPLEXITY;ALGORITHMS;COMPUTATIONS;PLANAR
日期:	1998
上传时间:	2010-06-29 20:15:17 (UTC+8)
出版者:	中央大學
摘要:	In this paper, we first develop a parallel algorithm for computing K-terminal reliability, denoted by R(G(K)), in 2-trees. Based on this result, we can also compute R(G(K)) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect to K-terminal reliability in partial 2-trees. Our algorithms take O(log n) time with C(m, n) processors on a CRCW PRAM, where C(m, n) is the number of processors required to find the connected components of a graph with m edges and n vertices in logarithmic lime. (C) 1998 Academic Press.
關聯:	JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
显示于类别:	[資訊工程研究所] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	426	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing