An efficient parallel algorithm for updating minimum spanning trees

DOI10.1016/0304-3975(88)90035-7zbMath0648.68075OpenAlexW1994693011MaRDI QIDQ1105383

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

updatingparallel algorithmtime complexityminimum spanning treeCREW-PRAM

Mathematics Subject Classification ID

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

Related Items (3)

Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph

Cites Work

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

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