A model classifying algorithms as inherently sequential with applications to graph searching

DOI10.1016/0890-5401(92)90033-CzbMath0767.68047OpenAlexW2007293413MaRDI QIDQ1187028

Raymond Greenlaw

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90033-c

zbMATH Keywords

breadth-first searchbreadth-depth searchinherently sequential

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Related Items (5)

A theory of strict P-completeness ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ The parallel complexity of approximating the high degree subgraph problem ⋮ Additive tree 2-spanners of permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parallel search algorithm for directed acyclic graphs
• Depth-first search is inherently sequential
• An introduction to parallelism in combinatorial optimization
• A random NC algorithm for depth first search
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• On uniform circuit complexity
• Parallel Depth-First Search in General Directed Graphs
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel algorithms for planar graph isomorphism and related problems
• Depth-First Search and Linear Graph Algorithms
• Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search

This page was built for publication: A model classifying algorithms as inherently sequential with applications to graph searching