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

Research output: Contribution to journalConference articlepeer-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 languageEnglish
Pages (from-to)603-607
Number of pages5
JournalProceedings of the International Parallel Processing Symposium, IPPS
Publication statusPublished - 1997 Jan 1
EventProceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 - Geneva, Switz
Duration: 1997 Apr 11997 Apr 5

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this