Natural cycletrees: Flexible interconnection graphs

Veanes, MargusUppsala universitet,Institutionen för ADB och datalogi (författare)

Natural cycletrees : Flexible interconnection graphs

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.

Barklund, JonasUppsala universitet,Institutionen för ADB och datalogi (författare)
Uppsala universitetInstitutionen för ADB och datalogi (creator_code:org_t)

Ingår i:Journal of Parallel and Distributed Computing: Elsevier BV33:1, s. 44-540743-73151096-0848

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.