Optimal randomized EREW PRAM algorithms for finding spanning forests

DOI10.1006/JAGM.2000.1146MaRDI QIDQ2731600zbMATH OpenOpenAlexWikidataFDO

Authors Shay Halperin, Uri Zwick

Publication date 20 September 2001

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2000.1146

zbMATH Keywords

Euler toursEulerian graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 871942
• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
• Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

Cited in

(6)

• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time
• Concurrent disjoint set union
• scientific article; zbMATH DE number 871942 (Why is no real title available?)
• scientific article; zbMATH DE number 1419215 (Why is no real title available?)
• COLORING ALGORITHMS ON SUBCUBIC GRAPHS

This page was built for publication: Optimal randomized EREW PRAM algorithms for finding spanning forests

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