HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Communication and Memory Optimized Tree Contraction and List Ranking

Jens Gustedt 1
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present a simple and efficient algorithm for the Tree Contraction Problem on a Coarse Grained $p$-Multiprocessor. With respect to its total computing time, its demand of memory and its total inter-processor communication it is only a small constant factor away from optimality. Unless traditional PRAM algorithms it doesn't use List Ranking as a necessary subroutine but specializes to List Ranking when applied to lists.
Document type :
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:19:09 AM
Last modification on : Friday, February 4, 2022 - 3:34:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:13:51 PM


  • HAL Id : inria-00072575, version 1



Jens Gustedt. Communication and Memory Optimized Tree Contraction and List Ranking. [Research Report] RR-4061, INRIA. 2000, pp.9. ⟨inria-00072575⟩



Record views


Files downloads