Communication-efficient parallel algorithms for distributed random-access machines

DOI10.1007/BF01762110zbMath0646.68067MaRDI QIDQ1104096

Charles E. Leiserson, Bruce M. Maggs

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsPRAMconservative algorithmdistributed random-access machinefat-treesload factormodel for parallel computationtree-contractiontreefix computationvolume-universal networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Methods for message routing in parallel machines, Improving multicut in directed trees by upgrading nodes, Efficient delay routing, Data independence of read, write, and control structures in PRAM computations, UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS, PERFORMANCE ANALYSIS OF WORMHOLE ROUTED K-Ary N-TREES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Three-Dimensional Circuit Layouts
• A Separator Theorem for Planar Graphs
• Parallel Prefix Computation
• A Regular Layout for Parallel Adders
• A Scheme for Fast Parallel Communication
• An O(logn) parallel connectivity algorithm
• The Parallel Evaluation of General Arithmetic Expressions
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations