Abstract
Metacyclic graphs, which include supertoroids as a subclass, have been shown to possess interesting properties and potential applications in implementing moderate- to large-size parallel processors with fairly small node degrees. Wu, Lakshmivarahan, and Dhall (J. Parallel Distrib. Comput. 60 (2000), pp. 539–565) have described a deterministic, distributed routing scheme for certain subclasses of metacyclic graphs. However, they offer no proof that the scheme is a shortest-path routing algorithm and do not indicate whether or how their scheme may be extended to the entire class of metacyclic graphs. In this paper, we provide a near-shortest-path, deterministic routing algorithm that is applicable to any metacyclic graph and derive a bound for the diameter of such graphs.
Acknowledgements
Detailed comments, offered in two rounds, by an anonymous reviewer have led to clear presentation and removal of some redundancies and errors. We are grateful for this reviewer's contributions. The research of W. Xiao has been supported by the Natural Science Foundation of Guangdong Province.