An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem

DOI10.1016/0020-0190(93)90019-6zbMath0768.68030OpenAlexW1970630246MaRDI QIDQ1209346

Francis Suraweera, Prabir Bhattacharya

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90019-6

zbMATH Keywords

complexitysortingparallel algorithmcomponentsminimum spanning treeundirected graphnon-numerical algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (3)

RNC-approximation algorithms for the steiner problem ⋮ An optimal PRAM algorithm for a spanning tree on trapezoid graphs. ⋮ An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs

Cites Work

• A parallel algorithm for eliminating cycles in undirected graphs
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Finding Minimum Spanning Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem