Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Let G be a connected, undirected and weighted graph with n vertices and m edges. A most vital edge of G with respect to minimum spanning tree is an edge whose removal from G results in the greatest weight-increase in the minimum spanning tree of the remaining graph. This paper presents a fast parallel algorithm that computes the most vital edge of G in O(log n) time using O(max{n, m log log log n/log n}) processors on a CRCW PRAM and O(log nlog log n) time using O(max{m, n2/(log n log log n)}) processors on an EREW PRAM respectively. It significantly improves the known results of O(log n) time and O(m) processors on the CRCW PRAM, and of O(log2n) time and O(n2/log2n) processors on the CREW PRAM, and O(n1+ε) time using n1-ε processors and O(m log(m/N)/N + nα(m, n)log(m/n)) time using N ≤ m log m/(nα(m, n)log(m/n)) processors on the EREW PRAM, respectively.

Original languageEnglish
Pages (from-to)129-136
Number of pages8
JournalInternational Journal of Computer Mathematics
Volume75
Issue number2
DOIs
Publication statusPublished - 2000
Externally publishedYes

Fingerprint

Dive into the research topics of 'Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree'. Together they form a unique fingerprint.

Cite this