Technical Report CS0520

TR#:CS0520
Class:CS
Title: Recognition of DFS Trees: Sequential and Parallel Algorithms with Refined Verifications
Authors: E. Korach and Z. Ostfeld
PDFCS0520.pdf
Abstract: The Depth First Search (DFS) algorithm is one of the basic techniques which is used in a very large variety of graph algorithms. Every application of the DFS involves, beside traversing the graph, constructing a special structured tree, called a DFS tree that may be used subsequently.

In a previous work we have shown that the family of graphs in which every spanning tree is a DFS tree is quite limited. Therefore the question: Given an undirected graph G = (V ,E) and an undirected spanning tree T, is T a DFS tree (T-DFS) in G ? was naturally raised and answered by sequential linear time algorithms. Here, a parallel algorithm which solves this problem in 0 (log|V|) time complexity and uses O(|E|) processors on a CREW PRAM, is presented. We also study the problem for directed graphs. A linear (O(|E|) time algorithm for solving it in the sequential case and a parallel implementation of it, which has O(log2|V|) time complexity and uses O (|V|^2.376) processors on a CREW PRAM, are presented.

An important feature of our algorithms, that we call refined verification, is that some of their decisions are endowed with proofs that can be verified with a better complexity than that of the algorithms themselves: In the undirected case, if the answer of the algorithm is positive then it outputs a proof for that fact that can be verined in O(t) time complexity with O(|E|/t) processors, where t>=log|V|, on a CREW PRAM. In the directed case, if T is not a DFS tree in G then the sequential algorithm supplies an o(|V|) time proof for that fact and the parallel implementation supplies a proof for that fact that can be verified in O(log|V|) time complexity with O( |V|) processors on a CREW PRAM. If T is a DFS tree in G then the parallel implementation of the algorithm outputs a proof that can be verified in O(t) time complexity with O(|E|/t) processors, where t>=log|V|, on a CREW PRAM.

Key words: acyclic graphs, DFS trees, graph algorithms, PRAM, parallel algorithms, refined verification.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0520), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion
admin