A Parallel Computation Approach to Topological Sorting

Open Access
Publisher Website
Google Scholar
Abstract
A new topological sorting algorithm is formulated using the parallel computation approach. The time complexity of this algorithm is of the order of the longest distance between a source node and a sink node in an acyclic digraph representing the partial orderings between elements. An implementation of this algorithm with an SIMD machine is discussed. To avoid contention for logical resources, a synchronization of all processors is proposed and its performance is also discussed.

This publication has 0 references indexed in Scilit: