A complexity theory of efficient parallel algorithms
From MaRDI portal
Publication:913512
DOI10.1016/0304-3975(90)90192-KzbMath0699.68069MaRDI QIDQ913512
Clyde P. Kruskal, Marc Snir, Larry Rudolph
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (24)
A theory of strict P-completeness ⋮ Strict sequential P-completeness ⋮ PRAM's towards realistic parallelism: BRAM's ⋮ MIMD VERSUS SIMD COMPUTATION: EXPERIENCE WITH NON-NUMERIC PARALLEL ALGORITHMS∗ † ⋮ Improved parallel integer sorting without concurrent writing ⋮ THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗† ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ Parallel local search ⋮ Efficient PRAM simulation on a distributed memory machine ⋮ The bulk-synchronous parallel random access machine ⋮ Parallel algorithms for certain matrix computations ⋮ Fast deterministic simulation of computations on faulty parallel machines ⋮ Low-contention data structures ⋮ Integer merging on EREW PRAM ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Efficient sampling of random permutations ⋮ Division in logspace-uniformNC1 ⋮ A tight analysis and near-optimal instances of the algorithm of Anderson and Woll ⋮ Polynomial hash functions are reliable ⋮ Parallel merging with restriction ⋮ A theory of strict P-completeness ⋮ Algorithms for the parallel alternating direction access machine ⋮ Improved fast integer sorting in linear space ⋮ Space-efficient parallel merging
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
- Size-depth trade-offs for monotone arithmetic circuits
- Sorting in \(c \log n\) parallel steps
- Depth-first search is inherently sequential
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- A random NC algorithm for depth first search
- The complexity of parallel search
- Optimal parallel selection has complexity O(log log N)
- On describing the behavior and implementation of distributed systems
- New hash functions and their use in authentication and set equality
- Towards a complexity theory of synchronous parallel computation
- Parallel computation and conflicts in memory access
- A note on \(N\)-body computations with cutoffs
- On the computational power of pushdown automata
- Bounding Fan-out in Logical Networks
- Fast Parallel Computation of Polynomials Using Few Processors
- Searching, Merging, and Sorting in Parallel Computation
- Dynamic parallel memories
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- On Parallel Searching
- Efficiency of Synchronous Versus Asynchronous Distributed Systems
- How to share memory in a distributed system
- Complexity Results for Permuting Data and Other Computations on Parallel Processors
- Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones
- Parallel Merge Sort
- Development of Parallel Methods for a $1024$-Processor Hypercube
- Sorting and Selecting in Rounds
- Efficient synchronization of multiprocessors with shared memory
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- A fast parallel algorithm for routing in permutation networks
- Ultracomputers
- Efficient parallel algorithms for some graph problems
- An O(logn) parallel connectivity algorithm
- Parallelism in Comparison Problems
- Fast Parallel Matrix Inversion Algorithms
- Optimal Sorting Algorithms for Parallel Computers
- Work-preserving emulations of fixed-connection networks
- The Parallel Evaluation of General Arithmetic Expressions
- New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
- A unified approach to models of synchronous parallel machines
- Parallelism in random access machines
- A Machine-Independent Theory of the Complexity of Recursive Functions
- An Adaptation of the Fast Fourier Transform for Parallel Processing
This page was built for publication: A complexity theory of efficient parallel algorithms
