Expected parallel time and sequential space complexity of graph and digraph problems

DOI10.1007/BF01758779zbMath0749.68059OpenAlexW1992595637MaRDI QIDQ1186789

John H. Reif, Paul G. Spirakis

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758779

zbMATH Keywords

upper boundsCREW PRAMCRCW PRAMundirected and directed random graph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (4)

A Glimpse at Paul G. Spirakis ⋮ Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time ⋮ A parallel algorithm for surface-based object reconstruction ⋮ An adaptive and cost-optimal parallel algorithm for minimum spanning trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Routing, merging, and sorting on parallel models of computation
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On uniform circuit complexity
• Towards a complexity theory of synchronous parallel computation
• Symmetric space-bounded computation
• Parallel computation and conflicts in memory access
• Parallel graph algorithms that are efficients on average
• Relationships between nondeterministic and deterministic tape complexities
• Deterministic coin tossing with applications to optimal parallel list ranking
• Symmetric Complementation
• Computing connected components on parallel computers
• Random Graph Isomorphism
• Finding the maximum, merging, and sorting in a parallel computation model
• Linear expected-time algorithms for connectivity problems
• Parallel Matrix and Graph Algorithms
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• An O(n2log n) parallel max-flow algorithm
• Efficient parallel algorithms for some graph problems
• A unified approach to models of synchronous parallel machines
• Parallelism in random access machines
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Expected parallel time and sequential space complexity of graph and digraph problems