Parallelism in random access machines

DOI10.1145/800133.804339zbMath1282.68104OpenAlexW2004618348MaRDI QIDQ5402548

James Wyllie, Steven Fortune

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/7454

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

On polynomial ideals, their complexity, and applications ⋮ SCHEDULING INTERVAL ORDERS IN PARALLEL ⋮ MODELS AND RESOURCE METRICS FOR PARALLEL AND DISTRIBUTED COMPUTATION∗ ⋮ Graph Connectivity in Log Steps Using Label Propagation ⋮ Membership in polynomial ideals over Q is exponential space complete ⋮ The parallel complexity of tree embedding problems (extended abstract) ⋮ Parallel recognition and ranking of context-free languages ⋮ Computation models and function algebras ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Nearly Work-Efficient Parallel Algorithm for Digraph Reachability ⋮ The complexity of synchronous iterative Do-All with crashes ⋮ Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines ⋮ On-line construction of two-dimensional suffix trees ⋮ An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups ⋮ The weakest specifunction ⋮ The complexity of ranking simple languages ⋮ Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries ⋮ Unnamed Item ⋮ Parallel algorithms for nevanlinna-pick interpolation:the scalar case^∗ ⋮ Distributed MST for constant diameter graphs ⋮ A theory of strict P-completeness ⋮ On the cost of iterative computations ⋮ Parallel random access machines with powerful instruction sets ⋮ Sequential and parallel algorithms for the NCA problem on pure pointer machines ⋮ A fast algorithm for scalar Nevanlinna-Pick interpolation ⋮ A parallel algorithm for computing Steiner trees in strongly chordal graphs ⋮ The parallel solution of domination problems on chordal and strongly chordal graphs ⋮ Routing, merging, and sorting on parallel models of computation ⋮ A parallel algorithm for the monadic unification problem ⋮ Finding least-weight subsequences with fewer processors ⋮ Parallel approximation schemes for subset sum and knapsack problems ⋮ Parallel pointer machines ⋮ A theory of strict P-completeness ⋮ A fixpoint theory for non-monotonic parallelism ⋮ The latency-of-data-access model for analyzing parallel computation ⋮ An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ Optimal parallel parsing of bracket languages ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ Array processing machines: an abstract model ⋮ Parallel time O(log n) recognition of unambiguous context-free languages ⋮ Formal specification of parallel SIMD execution ⋮ Parallelism and the maximal path problem ⋮ On nondeterminism in parallel computation ⋮ An optimal parallel algorithm for triangulating a set of points in the plane ⋮ A parallel algorithm for the maximal path problem ⋮ On the time required to sum n semigroup elements on a parallel machine with simultaneous writes ⋮ Optimal parallel randomized algorithms for sparse addition and identification ⋮ Data structures and algorithms for approximate string matching ⋮ An efficient parallel algorithm for updating minimum spanning trees ⋮ Parallel computation with threshold functions ⋮ Parallel O(log n) time edge-colouring of trees and Halin graphs ⋮ An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits ⋮ Parallel algorithms for finding Hamilton cycles in random graphs ⋮ Randomization and the parallel solution of linear algebra problems ⋮ Divide-and-conquer algorithms on the hypercube ⋮ A probabilistic simulation of PRAMs on a bounded degree network ⋮ An efficient parallel algorithm for planarity ⋮ Complexity theory of parallel time and hardware ⋮ Re-scheduling invocations of services for RPC grids ⋮ Parallel approximation algorithms for bin packing ⋮ An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm ⋮ On the relationship of congruence closure and unification ⋮ Efficient execution of nondeterministic parallel programs on asynchronous systems ⋮ A bridging model for multi-core computing ⋮ Graph coloring on coarse grained multicomputers ⋮ On uniform circuit complexity ⋮ Low-contention data structures ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ Parallelism and fast solution of linear systems ⋮ A new scheme for the deterministic simulation of PRAMs in VLSI ⋮ Parallel tree pattern matching ⋮ Division in idealized unit cost RAMs ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel models of computation: An introductory survey ⋮ The graph matching problem ⋮ A parallel method for fast and practical high-order Newton interpolation ⋮ Parallel computation and conflicts in memory access ⋮ Improved deterministic parallel integer sorting ⋮ Formula dissection: A parallel algorithm for constraint satisfaction ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Parallel cardinality stacks and an application ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Achieving optimal CRCW PRAM fault-tolerance ⋮ Parallel priority queues ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Reliable computations on faulty EREW PRAM ⋮ Fast rehashing in PRAM emulations ⋮ Efficient parallel algorithms can be made robust ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ Fast recognition of deterministic cfl's with a smaller number of processors ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ A note on the parallel complexity of anti-unification ⋮ Tight complexity bounds for term matching problems ⋮ An efficient parallel logarithmic time algorithm for the channel routing problem ⋮ Unambiguity of circuits ⋮ An efficient write-all algorithm for fail-stop PRAM without initialized memory ⋮ A tight analysis and near-optimal instances of the algorithm of Anderson and Woll ⋮ Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems ⋮ Sorting signed permutations by reversals, revisited ⋮ Parallel algorithms for a class of graphs generated recursively

This page was built for publication: Parallelism in random access machines