Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

DOI10.1109/31.1744MaRDI QIDQ3801099zbMATH OpenOpenAlexFDO

Authors Sajal K. Das, Narsingh Deo

Publication date 1988

Published in IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/31.1744

zbMATH Keywords

data structuresparallel algorithmsbipartitenessconnected componentsbridgesEREW PRAMfundamental cyclespanning forest

Mathematics Subject Classification ID

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

Recommendations

• Notes on 'divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model'
• PARALLEL ALGORITHMS FOR SOME DOMINANCE PROBLEMS BASED ON THE PRAM MODEL
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• Efficiently parallelizable problems on a class of decomposable graphs
• Divide-and-conquer and parallel graph reduction
• scientific article; zbMATH DE number 500370
• scientific article; zbMATH DE number 4068310
• scientific article; zbMATH DE number 4087453
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model

Cited in

(4)

• A unified approach to parallel depth-first traversals of general trees
• Notes on 'divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model'
• Optimal randomized EREW PRAM algorithms for finding spanning forests
• Stirling networks: A versatile combinatorial topology for multiprocessor systems

This page was built for publication: Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

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