Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
type: Item
instance of: scholarly article
title: Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
zbMATH Open document ID: 0787.68081
DOI: 10.1016/0012-365X(93)90375-4
author: Ephraim Korach
author: Zvi Ostfeld
published in: Discrete Mathematics
publication date: 1993-10-24T00:00:00Z
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)\) processo…
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 423584
zbMATH Keywords: acyclic graph
zbMATH Keywords: depth-first search
zbMATH Keywords: graph algorithms
zbMATH Keywords: DFS tree
zbMATH Keywords: parallel algorithm
zbMATH Keywords: CREW PRAM
zbMATH Keywords: refined verification
describes a project that uses: Algorithm 447
MaRDI profile type: Publication
cites work: A random NC algorithm for depth first search
cites work: Q4773298
cites work: A new distributed depth-first-search algorithm
cites work: Q3883524
cites work: On finding optimal and near-optimal lineal spanning trees
cites work: A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
cites work: Dividing a Graph into Triconnected Components
cites work: Efficient Planarity Testing
cites work: Parallel Prefix Computation
cites work: Depth-first search is inherently sequential
cites work: A parallel algorithm for recognizing unordered depth-first search
cites work: On Finding Lowest Common Ancestors: Simplification and Parallelization
cites work: Parallel Algorithms for Depth-First Searches I. Planar Graphs
cites work: Series - parallel graphs and depth-first search trees
cites work: Depth-First Search and Linear Graph Algorithms
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: An efficient parallel algorithm for shifting the root of a depth first spanning tree
cites work: On efficient parallel strong orientation
Recommended article: On the recognition of search trees generated by BFS and DFS
Recommended article: A parallel algorithm for recognizing unordered depth-first search
Recommended article: Parallel recognition algorithms for chordal-planar graphs and planar \(k\)-trees
Recommended article: Series - parallel graphs and depth-first search trees
Recommended article: The Recognition Problem of Graph Search Trees
Recommended article: Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata
Recommended article: A unified approach to parallel depth-first traversals of general trees
Recommended article: Automated Verification of Parallel Nested DFS
Recommended article: Recognizing breadth-first search trees in linear time
description: scientific article; zbMATH DE number 423584