Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
From MaRDI portal
Publication:1816995
DOI10.1007/BF01944354zbMath0860.68053OpenAlexW2147150816MaRDI QIDQ1816995
Donald B. Johnson, Panagiotis T. Metaxas
Publication date: 1 December 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01944354
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (3)
Variable neighborhood decomposition search for the edge weighted \(k\)-cardinality tree problem ⋮ Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph ⋮ Static and dynamic parallel computation of connected components
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic parallel list ranking
- An O(log n) algorithm for parallel update of minimum spanning trees
- Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Algorithms for updating minimal spanning trees
- Optimal parallel algorithms for multiple updates of minimum spanning trees
- An Efficient Parallel Biconnectivity Algorithm
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- Efficient parallel algorithms for some graph problems
- On Finding and Updating Spanning Trees and Shortest Paths
- The Parallel Evaluation of General Arithmetic Expressions
- A simple parallel tree contraction algorithm
This page was built for publication: Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
