Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072575
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:19:09 AM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:13:51 PM

Identifiers

  • HAL Id : inria-00072575, version 1

Collections

Citation

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

Share

Metrics

Record views

184

Files downloads

106