1995 | ReviewPaper | Buchkapitel
Time-optimal tree computations on sparse meshes
verfasst von : D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some treerelated computations. We view our contribution at two levels: on the one hand we exhibit time lower bounds for a number of tree-related problems both on the CREW-PRAM and on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite number of processors. We then go on to show that this lower bound is tight. We also show that the task of reconstructing n-node binary trees from their traversais can be performed in O(1) time on the same architecture. Our algorithms rely on novel time-optimal algorithms on sequences of parentheses that we also develop.