An O(log n) algorithm for parallel update of minimum spanning trees

DOI10.1016/0020-0190(86)90098-0zbMath0592.68061OpenAlexW2080566336MaRDI QIDQ1075769

I. V. Ramakrishnan, Shaunak R. Pawagi

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90098-0

zbMATH Keywords

graph algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

An O(log n) algorithm for parallel update of minimum spanning trees ⋮ Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ On handling vertex deletion in updating minimum spanning trees ⋮ An efficient parallel algorithm for updating minimum spanning trees ⋮ Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Static and dynamic parallel computation of connected components

Cites Work

• An O(log n) algorithm for parallel update of minimum spanning trees
• Algorithms for updating minimal spanning trees
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• On Finding and Updating Spanning Trees and Shortest Paths
• Implementation of simultaneous memory address access in models that forbid it

This page was built for publication: An O(log n) algorithm for parallel update of minimum spanning trees