Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees

DOI10.1016/0020-0190(88)90084-1zbMath0637.68046OpenAlexW2065634943MaRDI QIDQ1098631

Kurt Mehlhorn, Hermann Jung

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90084-1

zbMATH Keywords

parallel algorithmminimum spanning treesindependent sets in trees

Mathematics Subject Classification ID

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

Related Items

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 ⋮ 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

• Faster optimal parallel prefix sums and list ranking
• An Efficient Parallel Biconnectivity Algorithm
• Deterministic coin tossing with applications to optimal parallel list ranking
• Unnamed Item