A random NC algorithm for depth first search
type: Item
instance of: scholarly article
title: A random NC algorithm for depth first search
zbMATH Open document ID: 0647.68060
DOI: 10.1007/BF02122548
author: S. H. Smith
published in: Combinatorica
publication date: 1988-01-01T00:00:00Z
review text: We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \(O(T_{MM}(n)\log^ 3 n)\), and the number of processors used is \(P_{MM}(n)\) where \(T_{MM}n)\) and \(P_{MM}(n)\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4057019
zbMATH Keywords: random NC algorithm
zbMATH Keywords: depth first search tree
zbMATH Keywords: undirected graph
zbMATH Keywords: P-RAM
zbMATH Keywords: minimum weight perfect matching
Wikidata QID: Q56114900
MaRDI profile type: Publication
cites work: A parallel algorithm for the maximal path problem
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4195963
cites work: Network Flow and Testing Graph Connectivity
cites work: A parallel search algorithm for directed acyclic graphs
cites work: Constructing a perfect matching is in random NC
cites work: A fast parallel algorithm for the maximal independent set problem
cites work: A Separator Theorem for Planar Graphs
cites work: Matching is as easy as matrix inversion
cites work: Parallel Computations in Graph Theory
cites work: Depth-first search is inherently sequential
cites work: Parallel Algorithms for Depth-First Searches I. Planar Graphs
cites work: Depth-First Search and Linear Graph Algorithms
full work available at URL: https://doi.org/10.1007/bf02122548
OpenAlex ID: W2049327803
description: scientific article; zbMATH DE number 4057019