Incomparability in parallel computation

DOI10.1016/0166-218X(90)90082-NzbMath0707.68033MaRDI QIDQ919822

Vince Grolmusz, Prabhakar Ragde

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

parallel computationlower boundARBITRARY-modelCANCELLATION-modelCOLLISION modelcommon-modelconcurrent-write PRAMsErdős-Rado intersecting set theoremTurán's theorem for graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Parallel algorithms for separable permutations ⋮ Large parallel machines can be extremely slow for small problems

Cites Work

• Unnamed Item
• Unnamed Item
• Simulations among concurrent-write PRAMs
• Parallel computation and conflicts in memory access
• Intersection Theorems for Systems of Sets
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching
• Finding the maximum, merging, and sorting in a parallel computation model
• A universal interconnection pattern for parallel computers
• An O(logn) parallel connectivity algorithm
• Optimal bounds for decision problems on the CRCW PRAM
• Implementation of simultaneous memory address access in models that forbid it

This page was built for publication: Incomparability in parallel computation