Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

B. Dixon, R. E. Tarjan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in O(log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.

Original languageEnglish (US)
Pages (from-to)11-18
Number of pages8
JournalAlgorithmica (New York)
Volume17
Issue number1
DOIs
StatePublished - Jan 1997

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Minimum spanning tree
  • Network optimization
  • Sensitivity analysis
  • Verification algorithms

Fingerprint Dive into the research topics of 'Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time'. Together they form a unique fingerprint.

Cite this