A random NC algorithm for depth first search
From MaRDI portal
Publication:1104756
DOI10.1007/BF02122548zbMath0647.68060WikidataQ56114900 ScholiaQ56114900MaRDI QIDQ1104756
Publication date: 1988
Published in: Combinatorica (Search for Journal in Brave)
undirected graph; P-RAM; minimum weight perfect matching; depth first search tree; random NC algorithm
DB lookup for MSC labels failed
Related Items
Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Parallel complexity of computing a maximal set of disjoint paths, A model classifying algorithms as inherently sequential with applications to graph searching, Not all planar digraphs have small cycle separators, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, A remark on maximum matching of line graphs, An optimal parallel algorithm for planar cycle separators, Designing checkers for programs that run in parallel