Embedding of congestion-free complete binary trees with dilation two in star graphs

Yuh Shyan Chen, Yu-Chee Tseng, Tong Ying Juang, Chiou Jyu Chang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Trees are a common structure to represent the inter-task communication pattern of a parallel algorithm. In this paper, we consider the problem of embedding a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop a congestion-free, dilation-2, load-1 embedding of a level-p binary tree into an n-dimensional star graph, where p=Σ/sub i=2/ n [log i] and k is any positive integer. The result offers a tree of size comparable or superior to existing results, but with less congestion and dilation.

Original languageEnglish
Title of host publication1997 3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997
EditorsWanlei Zhou, Andrzej Goscinski, Michael Hobbs
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages331-344
Number of pages14
ISBN (Electronic)0780342291, 9780780342293
DOIs
StatePublished - 1 Jan 1997
Event3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997 - Melbourne, Australia
Duration: 10 Dec 199712 Dec 1997

Publication series

Name1997 3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997

Conference

Conference3rd International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 1997
CountryAustralia
CityMelbourne
Period10/12/9712/12/97

Fingerprint Dive into the research topics of 'Embedding of congestion-free complete binary trees with dilation two in star graphs'. Together they form a unique fingerprint.

Cite this