Natural cycletrees: Flexible interconnection graphs
1996 (English)In: Journal of Parallel and Distributed Computing, ISSN 0743-7315, E-ISSN 1096-0848, Vol. 33, no 1, 44-54 p.Article in journal (Refereed) Published
Natural cycletrees, formally defined in this paper, is a subclass of Hamiltonian graphs with maximum degree 3 that contain a binary spanning tree. A natural cycletree used as an interconnection network thus supports directly broadcasting through the binary tree as well as nearest-neighbor communication through the cycle. Natural cycletrees have several other interesting properties; e.g., they are planar, easily extensible, and can be contracted using the same methods as for binary trees. The main results of the paper are: (i) Given an arbitrary basic binary spanning treeT, there exists a natural cycletree with a minimal number of edges forT. (ii) A natural cycletree has a very simple router. We give a superfast parallel algorithm that can establish near optimal router data for that router.
Place, publisher, year, edition, pages
1996. Vol. 33, no 1, 44-54 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-27249DOI: 10.1006/jpdc.1996.0023OAI: oai:DiVA.org:uu-27249DiVA: diva2:55143