Journal article
Parallel Algorithms for Depth-First Searches I. Planar Graphs
SIAM journal on computing, v 15(3), pp 814-830
01 Aug 1986
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
This paper presents an unbounded-parallel algorithm for performing a depth-first search of a planar undirected graph. The algorithm uses $O(n^4 )$ processors and executes in $O(\log ^3 n)$-time. It had previously been conjectured that the problem of computing a depth-first spanning tree was inherently sequential.
Metrics
Details
- Title
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Creators
- Justin R SmithDept. of Mathematics and Computer Science, Drexel Univ., Philadelphia, PA
- Publication Details
- SIAM journal on computing, v 15(3), pp 814-830
- Publisher
- Society for Industrial and Applied Mathematics
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- [Retired Faculty]
- Web of Science ID
- WOS:A1986D484700013
- Scopus ID
- 2-s2.0-0022768953
- Other Identifier
- 991019184288404721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied