𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Construction of natural cycletrees

✍ Scribed by Margus Veanes; Jonas Barklund

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
488 KB
Volume
60
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, the following question is answered: Given a cycle C, of size N, how can one compute, in O(N) time, a minimal set of edges E such that adjoining E to the cycle yields a graph with a binary spanning tree having minimal total path length? The answer is given through an algorithm for top-down construction of natural cycletrees, where the structure of each subtree is restricted by a split relation between certain properties of the subtree.

πŸ“œ SIMILAR VOLUMES

Natural Cycletrees: Flexible Interconnec
Natural Cycletrees: Flexible Interconnection Graphs
✍ Margus Veanes; Jonas Barklund πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 500 KB

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 communicat

On the number of edges in cycletrees
On the number of edges in cycletrees
✍ Margus Veanes; Jonas Barklund πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 436 KB