Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

DOI10.1016/0012-365X(93)90375-4MaRDI QIDQ685690zbMATH OpenFDO

Authors Ephraim Korach, Zvi Ostfeld

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90375-4

zbMATH Keywords

acyclic graphCREW PRAMdepth-first searchDFS treegraph algorithmsparallel algorithmrefined verification

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Review text

The depth-first search (DFS) algorithm is one of the basic techniques used in a very large variety of graph algorithms. Every application of the DFS involves, besides 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 we present a parallel algorithm which solves this problem in \(O(t)\) time complexity and uses \(O(| E|/t)\) processors, where \(t \geq \log| V|\), on a CREW PRAM. 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(\log^ 2| 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 negative then it outputs a proof for the fact that can be verified in \(O(t)\) time complexity with \(O(| V|/t)\) processors, where \(t\geq \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 the fact that can be verified in \(O(t)\) time complexity with \(O(| V|/t)\) processors, where \(t\geq \log| V|\), 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\geq \log| V|\), on a CREW PRAM. Hence, all the verifications have an optimal speed-up.

Recommendations

• On the recognition of search trees generated by BFS and DFS
• A parallel algorithm for recognizing unordered depth-first search
• Parallel recognition algorithms for chordal-planar graphs and planar k-trees
• Series - parallel graphs and depth-first search trees
• The recognition problem of graph search trees
• Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
• A unified approach to parallel depth-first traversals of general trees
• Automated verification of parallel nested DFS
• Recognizing breadth-first search trees in linear time

Cites work

• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A new distributed depth-first-search algorithm
• A parallel algorithm for recognizing unordered depth-first search
• A random NC algorithm for depth first search
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• An Efficient Parallel Biconnectivity Algorithm
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• On efficient parallel strong orientation
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On finding optimal and near-optimal lineal spanning trees
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel Prefix Computation
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Series - parallel graphs and depth-first search trees

Cited in

(8)

• Depth-first search is inherently sequential
• A new distributed depth-first-search algorithm
• A parallel algorithm for recognizing unordered depth-first search
• On the recognition of search trees generated by BFS and DFS
• Series - parallel graphs and depth-first search trees
• The recognition problem of graph search trees
• DFS tree construction: Algorithms and characterizations
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

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