Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
type: Item
instance of: scholarly article
title: Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
zbMATH Open document ID: 0795.68086
DOI: 10.1016/0022-0000(93)90042-U
author: Ming-Yang Kao
author: Philip N. Klein
published in: Journal of Computer and System Sciences
publication date: 1994-09-18T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 529951
zbMATH Keywords: transitive closure
zbMATH Keywords: parallel algorithms
zbMATH Keywords: planar digraphs
zbMATH Keywords: digraph reachability
MaRDI profile type: Publication
cites work: A simple parallel tree contraction algorithm
cites work: A random NC algorithm for depth first search
cites work: Parallel Depth-First Search in General Directed Graphs
cites work: Q4091421
cites work: Deterministic parallel list ranking
cites work: Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
cites work: Q3097395
cites work: The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
cites work: Faster optimal parallel prefix sums and list ranking
cites work: Q3761691
cites work: Parallel concepts in graph theory
cites work: A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
cites work: Parallel algorithms for planar graph isomorphism and related problems
cites work: Improved algorithms for graph four-connectivity
cites work: Q3798260
cites work: Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
cites work: Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
cites work: An efficient parallel algorithm for planarity
cites work: Q3798226
cites work: Parallel Prefix Computation
cites work: A Separator Theorem for Planar Graphs
cites work: Parallel ear decomposition search (EDS) and st-numbering in graphs
cites work: Finding small simple cycle separators for 2-connected planar graphs
cites work: Fast and efficient solution of path algebra problems
cites work: Q3795246
cites work: Depth-first search is inherently sequential
cites work: An O(logn) parallel connectivity algorithm
cites work: Parallel Algorithms for Depth-First Searches I. Planar Graphs
cites work: Parallel Transitive Closure and Point Location in Planar Structures
cites work: Depth-First Search and Linear Graph Algorithms
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Q3798261
full work available at URL: 0022-0000(93)90042-u
OpenAlex ID: W4242757385
description: scientific article; zbMATH DE number 529951