An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs

DOI10.1016/S0020-0190(97)00009-4MaRDI QIDQ290218zbMATH OpenOpenAlexFDO

Authors H. S. Chao, F. R. Hsu, R. C. T. Lee

Publication date 1 June 2016

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

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00009-4

zbMATH Keywords

breadth-first search treesparallel algorithmspermutation graphs

Mathematics Subject Classification ID

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

Recommendations

• Efficient parallel algorithms for permutation graphs
• scientific article; zbMATH DE number 4172414
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Parallel breadth-first search algorithms for trees and graphs
• An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Efficient parallel algorithms for permutation graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)

Cited in

(5)

• An improved parallel algorithm that computes the BFS numbering of a directed graph
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Parallel breadth-first search algorithms for trees and graphs
• Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs
• Unrestricted and complete breadth-first search of trapezoid graphs in O(n) time

This page was built for publication: An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs

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