Optimal bounds for decision problems on the CRCW PRAM
From MaRDI portal
Publication:4710686
Recommendations
Cited in
(49)- Sorting and searching revisted
- Improved deterministic parallel integer sorting
- A sublogarithmic convex hull algorithm
- Lower bounds for recognizing small cliques on CRCW PRAM's
- Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes
- More efficient parallel flow algorithms
- Optimal parallel time bounds for the maximum clique problem on intervals
- Limitations of the QRQW and EREW PRAM models
- Efficient parallel algorithms can be made robust
- Coloring permutation graphs in parallel
- Exponential lower bounds for the pigeonhole principle
- Optimal circular arc representations: Properties, recognition, and construction
- Optimal parallel algorithms for periods, palindromes and squares (extended abstract)
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- The complexity of parallel prefix problems on small domains
- \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
- scientific article; zbMATH DE number 2013188 (Why is no real title available?)
- An insight on PRAM computational bounds
- Transforming comparison model lower bounds to the parallel-random-access-machine
- Designing checkers for programs that run in parallel
- PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
- SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS
- ON THE POWER OF SOME PRAM MODELS
- Simulation of PRAMs with scan primitives by unbounded fan-in circuits
- MATRIX OPERATIONS USING ARRAYS WITH RECONFIGURABLE OPTICAL BUSES∗
- Integer summing algorithms on reconfigurable meshes
- The queue-read queue-write asynchronous PRAM model
- Time lower bounds do not exist for CRCW PRAMs
- Sorting on PRAMs with reconfigurable buses
- On the Parallel Evaluation of Dwba Integrals
- \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM
- OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- Constant-time parallel recognition of split graphs
- FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
- Designing algorithms by expectations
- Sorting in linear time?
- An exponential separation between the parity principle and the pigeonhole principle
- Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
- The parallel complexity of integer prefix summation
- On a compaction theorem of Ragde
- scientific article; zbMATH DE number 7561507 (Why is no real title available?)
- Round compression for parallel matching algorithms
- Matching parentheses in parallel
- NEXP does not have non-uniform quasipolynomial-size ACC circuits of \(o(\log \log n)\) depth
- Incomparability in parallel computation
- Scalable algorithms for the mesh with buses: merging, sorting and selection
- Fast parallel Lyndon factorization with applications
- Integer sorting and routing in arrays with reconfigurable optical buses
This page was built for publication: Optimal bounds for decision problems on the CRCW PRAM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4710686)
