An 0(log n) parallel algorithm for strong connectivity augmentation problem

DOI10.1080/00207168708803592MaRDI QIDQ3804208zbMATH OpenOpenAlexWikidataFDO

Authors Pranay Chaudhuri

Publication date 1987

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168708803592

zbMATH Keywords

augmentationCRCW PRAMparallel algorithmparallel random access machinestrong connectivitytime complexity

Mathematics Subject Classification ID

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

Recommendations

• An optimal parallel connectivity algorithm
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• scientific article; zbMATH DE number 1979724
• Parallel algorithms for connectivity problems in graph theory
• An optimal parallel processor bound in strong orientation of an undirected graph

Cites work

• Augmentation Problems
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Finding the maximum, merging, and sorting in a parallel computation model
• scientific article; zbMATH DE number 3635515 (Why is no real title available?)
• Parallel computation and conflicts in memory access
• Parallel Computations in Graph Theory

Cited in

(6)

• Fast parallel graph searching with applications
• Fast parallel strong orientation of mixed graphs and related augmentation problems
• scientific article; zbMATH DE number 1979724 (Why is no real title available?)
• FINDING CENTERS AND MEDIANS OF GRAPHS IN PARALLEL
• Distributed graph augmentation protocols to achieve strong connectivity in multi-agent networks
• An adaptive parallel algorithm for analyzing activity networks

This page was built for publication: An 0(log n) parallel algorithm for strong connectivity augmentation problem

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