Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees

Chin Wen Ho; Sun Yuan Hsieh; Gen Huey Chen

Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees

Chin Wen Ho, Sun Yuan Hsieh, Gen Huey Chen

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Conference article › peer-review

Abstract

We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge 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 connected components of a graph with m edges and n vertices in logarithmic time.

Original language	English
Pages (from-to)	603-607
Number of pages	5
Journal	Proceedings of the International Parallel Processing Symposium, IPPS
State	Published - 1997
Event	Proceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 - Geneva, Switz Duration: 1 Apr 1997 → 5 Apr 1997

Cite this

@article{b01bd868e22343f697db8b6e8d157f67,

title = "Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees",

abstract = "We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge 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 connected components of a graph with m edges and n vertices in logarithmic time.",

author = "Ho, {Chin Wen} and Hsieh, {Sun Yuan} and Chen, {Gen Huey}",

year = "1997",

language = "???core.languages.en_GB???",

pages = "603--607",

journal = "Proceedings of the International Parallel Processing Symposium, IPPS",

issn = "1063-7133",

note = "Proceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 ; Conference date: 01-04-1997 Through 05-04-1997",

}

TY - JOUR

T1 - Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees

AU - Ho, Chin Wen

AU - Hsieh, Sun Yuan

AU - Chen, Gen Huey

PY - 1997

Y1 - 1997

N2 - We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge 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 connected components of a graph with m edges and n vertices in logarithmic time.

AB - We develop a parallel strategy to compute K-terminal reliability in 2-trees and partial 2-trees. We also solve the problem of finding the most vital edge 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 connected components of a graph with m edges and n vertices in logarithmic time.

UR - http://www.scopus.com/inward/record.url?scp=0030646763&partnerID=8YFLogxK

M3 - 會議論文

AN - SCOPUS:0030646763

SN - 1063-7133

SP - 603

EP - 607

JO - Proceedings of the International Parallel Processing Symposium, IPPS

JF - Proceedings of the International Parallel Processing Symposium, IPPS

T2 - Proceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97

Y2 - 1 April 1997 through 5 April 1997

ER -

Efficient parallel strategy for computing K-terminal reliability and finding most vital edge in 2-trees and partial 2-trees

Abstract

Fingerprint

Cite this