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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29165

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29165

Title:	An efficient parallel strategy for computing K-terminal reliability and finding most vital edges in 2-trees and partial 2-trees
Authors:	Ho,CW;Hsieh,SY;Chen,GH
Contributors:	資訊工程研究所
Keywords:	STEINER TREES;NETWORKS;GRAPHS;COMPLEXITY;ALGORITHMS;COMPUTATIONS;PLANAR
Date:	1998
Issue Date:	2010-06-29 20:15:17 (UTC+8)
Publisher:	中央大學
Abstract:	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.
Relation:	JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	434	View/Open

社群 sharing