A parallel search algorithm for directed acyclic graphs |
| |
| Authors: | Ratan K Ghosh G P Bhattacharjee |
| |
| Institution: | (1) Mathematics Department, Indian Institute of Technology, 721302 Kharagpur, India |
| |
| Abstract: | A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)2) whenO(n
2.81/logn) processors are used. |
| |
| Keywords: | Parallel algorithm depth-first antilexicographic graph search acyclic spanning tree traversal preorder rpostorder |
| 本文献已被 SpringerLink 等数据库收录！ |
