uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Natural cycletrees: Flexible interconnection graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Computing Science Department.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Computing Science Department.
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
Abstract [en]

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.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-27249DOI: 10.1006/jpdc.1996.0023OAI: oai:DiVA.org:uu-27249DiVA: diva2:55143
Available from: 2008-10-17 Created: 2008-10-17 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Computing Science Department
In the same journal
Journal of Parallel and Distributed Computing
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 430 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf