An efficient parallel algorithm for updating minimum spanning trees

DOI10.1016/0304-3975(88)90035-7MaRDI QIDQ1105383zbMATH OpenOpenAlexFDO

Authors Kshitij Doshi, Peter J. Varman

Publication date 1988

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(88)90035-7

zbMATH Keywords

minimum spanning treeparallel algorithmtime complexityupdatingCREW-PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Optimal parallel algorithms for multiple updates of minimum spanning trees
• An efficient parallel algorithm for multiple edge updates of minimum spanning trees on sparse graphs
• A Parallel Algorithm for Computing Minimum Spanning Trees
• scientific article; zbMATH DE number 4199627
• Improving the efficiency of parallel minimum spanning tree algorithms
• scientific article; zbMATH DE number 24457
• scientific article; zbMATH DE number 1556480
• An adaptive and cost-optimal parallel algorithm for minimum spanning trees

Cites work

• A Separator Theorem for Planar Graphs
• Algorithms for updating minimal spanning trees
• An O(log n) algorithm for parallel update of minimum spanning trees
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Efficient parallel algorithms for some graph problems
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• On Finding and Updating Spanning Trees and Shortest Paths
• On efficient parallel strong orientation
• Parallelism in random access machines

Cited in

(12)

• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Fast updating of well-balanced trees
• Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
• An efficient parallel algorithm for multiple edge updates of minimum spanning trees on sparse graphs
• Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph
• scientific article; zbMATH DE number 708844 (Why is no real title available?)
• scientific article; zbMATH DE number 3965451 (Why is no real title available?)
• A subtree-partitioning algorithm for inducing parallelism in network simplex dual updates
• scientific article; zbMATH DE number 3956442 (Why is no real title available?)
• scientific article; zbMATH DE number 4199627 (Why is no real title available?)

This page was built for publication: An efficient parallel algorithm for updating minimum spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105383)