Cycletrees: a Novel Class of Interconnection Graphs

We introduce a new class of graphs that we call cycletrees. A cycletree includes a basic binary tree and has a unique Hamiltonian cycle. We argue that cycletrees reflect the communication patterns of several common parallel programming paradigms and can be used in various fields of parallel computation. Several minimality, optimality and planarity properties are proved for cycletrees. A subclass of cycletrees is identified as natural cycletrees through an inductive definition. Methods for generating natural cycletrees, given either a set of vertices, a cycle or a basic binary tree, are presented. We present an inexpensive and simple routing algorithm for natural cycletree networks. A superfast parallel algorithm is presented, which dynamically establishes the shortest path router data for the given router algorithm. We compare cycletrees with other interconnection graphs that have been designed for partly similar reasons.