- 作者：R. Krá ; lovič ; ; P. Ruž ; ič ; ka
- 关键词：Communication networks ; Packet routing ; Acyclic orientation cover
- 刊名：Theoretical Computer Science
- 出版年：2007
- 出版时间：20 April 2007
- 年：2007
- 卷：374
- 期：1-3
- 页码：203-213
- 全文大小：531 K
This acyclic orientation covering problem on the shortest path systems has been studied in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] where it was shown that the general problem of determining the rank is NP-complete and some upper and lower bounds on the rank were presented for particular topologies, such as grids, tori and hypercubes. The main unresolved problem stated in [J.-C. Bermond, M. Di Ianni, M. Flammini, S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in: 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), in: Lecture Notes in Computer Science, vol. 1335, Springer-Verlag, 1997, pp. 52–64] was to determine the rank values for other well-known interconnection networks and also for more general classes of graphs.
In this paper we give a general lower bound argument for the rank problem and apply it to the class of involution-generated Cayley graphs which among others include hypercubes, star graphs, pancake graphs and transposition-tree based graphs [S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38 (4) (1989) 555–565]. We also present a large class of graphs with constant rank. This class of graphs is defined as the layered cross product [S. Even, A. Litman, Layered cross product—A technique to construct interconnection networks, Networks 29 (1997) 219–223] of layered trees and series–parallel graphs and includes among others butterflies, Beneš networks, fat-trees and meshes of trees. For some special topologies, improved lower bounds on the rank are also presented. We consider some of the modified versions of the rank problem as well.