Technical Report CS0515

Title: DFS Tree Construction: Algorithms and Characterizations (Extended Version of TR #470)
Authors: E. Korach and Z. Ostfeld
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. In this paper, we give a complete characterization of all the graphs in which every spanning tree is a DFS tree. These graphs are called Total-DFS-Graphs. The characterization we present show that a large variety of graphs are not Total-DFS-Graphs, and therefore the following question is naturally raised: Given an undirected graph G=(V,E) and an undirecttd spanning tree T, is T a DFS tree of G? We give an algorithm to answer this question in linear (O(|E|)) time. An important feature of the algorithm is that if the answer is negative then it provides a short (O(|V|)) proof for that fact.
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 (, 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