Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

DOI10.1007/BF01944354MaRDI QIDQ1816995zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

minimum spanning treevertex updating problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3956442
• An efficient parallel algorithm for updating minimum spanning trees
• 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

Cites work

• A simple parallel tree contraction algorithm
• Algorithms for updating minimal spanning trees
• An Efficient Parallel Biconnectivity Algorithm
• An O(log n) algorithm for parallel update of minimum spanning trees
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Deterministic parallel list ranking
• Efficient parallel algorithms for some graph problems
• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3956442 (Why is no real title available?)
• scientific article; zbMATH DE number 4011928 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• On Finding and Updating Spanning Trees and Shortest Paths
• Optimal parallel algorithms for multiple updates 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
• The Parallel Evaluation of General Arithmetic Expressions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(12)

• Static and dynamic parallel computation of connected components
• Upgrading min-max spanning tree problem under various cost functions
• Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph
• An efficient parallel algorithm for multiple edge updates of minimum spanning trees on sparse graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• scientific article; zbMATH DE number 3956442 (Why is no real title available?)
• scientific article; zbMATH DE number 3965451 (Why is no real title available?)
• Incremental distributed asynchronous algorithm for minimum spanning trees
• scientific article; zbMATH DE number 554530 (Why is no real title available?)
• scientific article; zbMATH DE number 708844 (Why is no real title available?)

This page was built for publication: Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

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