Sökning: onr:"swepub:oai:DiVA.org:uu-27249" >
Natural cycletrees :
Natural cycletrees : Flexible interconnection graphs
-
- Veanes, Margus (författare)
- Uppsala universitet,Institutionen för ADB och datalogi
-
- Barklund, Jonas (författare)
- Uppsala universitet,Institutionen för ADB och datalogi
-
(creator_code:org_t)
- Elsevier BV, 1996
- 1996
- Engelska.
-
Ingår i: Journal of Parallel and Distributed Computing. - : Elsevier BV. - 0743-7315 .- 1096-0848. ; 33:1, s. 44-54
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas