Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

B. Dixon, R. E. Tarjan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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)
Issue number1
StatePublished - Jan 1997

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


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


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

Cite this