Parallel computation and conflicts in memory access
From MaRDI portal
Publication:1171382
DOI10.1016/0020-0190(82)90093-XzbMath0498.68029OpenAlexW2049628259MaRDI QIDQ1171382
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90093-x
parallel computationgraph algorithmsmodel of computationparallel RAMparallel time complexityconflict-resolution rules in an idealized concurrent environment
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)
Related Items
A new class of parallel algorithms for finding connected components on machines with bit-vector operations, Computing OR on a randomized fixed adversary CRCW PRAM, Finding maximum matching for bipartite graphs in parallel, Constant-time parallel recognition of split graphs, Towards optimal parallel bucket sorting, Limits on the power of concurrent-write parallel machines, Fast parallel graph searching with applications, Simulations among concurrent-write PRAMs, Computing dominators in parallel, FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS, PARALLEL BLOCK-FINDING USING DISTANCE MATRICES, FINDING CENTERS AND MEDIANS OF GRAPHS IN PARALLEL, A parallel bucket sort, On efficient parallel computations for some dynamic programming problems, On the Parallel Evaluation of Dwba Integrals, Fast and optimal simulations between CRCW PRAMs, Parallel computations on graphs, Removing Ramsey theory: Lower bounds with smaller domain size, Coloring k-colorable graphs in constant expected parallel time, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, A complexity theory of efficient parallel algorithms, Two dimensional processor array with a reconfigurable bus system is at least as powerful as CRCW model, Incomparability in parallel computation, Fast sequential and parallel algorithms for finding extremal sets, An 0(log n) parallel algorithm for strong connectivity augmentation problem, Relating the power of the multiple associative computing (MASC) model to that of reconfigurable bus-based models, Reducing conflict resolution time for solving graph problems in broadcast communications, Processor-time tradeoffs in PRAM simulations, Expected parallel time and sequential space complexity of graph and digraph problems, A parallel algorithm for surface-based object reconstruction, An improved parallel algorithm for integer GCD, Fast parallel heuristics for the job shop scheduling problem, New fast parallel algorithm for the connected component problem and its VLSI implementation, Parallel random access machines with bounded memory wordsize, Simulating the CRCW PRAM on reconfigurable networks, Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS, An adaptive and cost-optimal parallel algorithm for minimum spanning trees, Large parallel machines can be extremely slow for small problems, On the complexity of the recognition of parallel 2D-image languages, Computing transitive closure on systolic arrays of fixed size
Cites Work
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Corrigendum: A fast stable sorting algorithm with absolutely minimum storage
- Finding the maximum, merging, and sorting in a parallel computation model
- Parallel Algorithms in Graph Theory: Planarity Testing
- Some Complexity Results for Matrix Computations on Parallel Processors
- Parallelism in random access machines
