A random NC algorithm for depth first search

A random NC algorithm for depth first search
复制标题

一种深度优先搜索的随机 NC 算法

DOI：
--
复制
发表时间：
1987
期刊：
Comb.
影响因子：
--
通讯作者：
Richard J. Anderson
Richard J. Anderson
中科院分区：
--
文献类型：
--
作者：
A. Aggarwal;Richard J. Anderson

文献摘要

被引文献

相似文献

在本文中，我们提出了一种快速并行算法，用于为无向图构建深度优先搜索树。该算法是一种 RNC 算法，这意味着它是一种概率算法，使用 P-RAM 上的多项式数量的处理器以多对数时间运行。该算法的运行时间为∽(TMM(n)log3n)，所使用的处理器数量为PMM(n)，其中TMM(n)和PMM(n)是在具有最大边权重n的n个顶点图上找到最小权重完美匹配所需的时间和处理器数量。
In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm 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 &Ogr;(TMM(n)log3n), and the number of processors used is PMM(n) where TMM(n) and PMM(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.