A new family of Cayley graph interconnection networks of constant degree four
作者： P. Vadapalli , P.K. Srimani
DOI: 10.1109/71.481595
关键词: Regular graph 、 Cayley graph 、 Routing (electronic design automation) 、 Discrete mathematics 、 Computer science 、 Graph 、 Degree (graph theory) 、 Parallel algorithm 、 Graph theory 、 Distributed computing 、 Vertex-transitive graph 、 Constant (mathematics) 、 Degree distribution
摘要: We propose a new family of interconnection networks that are Cayley graphs with constant node degree 4. These regular, have logarithmic diameter, and maximally fault tolerant. investigate different algebraic properties these (including tolerance) optimal routing algorithms. As far as we know, this is the first
acm.org
ieeecomputersociety.org
computer.org参考文章(21)
Balakrishnan Krishnamurthy, Dov Harel, Sheldon B. Akers, The Star Graph: An Attractive Alternative to the n-Cube. international conference on parallel processing. pp. 393- 400 ,(1987)
Guha, Sen, On Fault-Tolerant Distributor Communication Architecture IEEE Transactions on Computers. ,vol. 35, pp. 281- 283 ,(1986) , 10.1109/TC.1986.1676752
Pradhan, Reddy, A Fault-Tolerant Communication Architecture for Distributed Systems IEEE Transactions on Computers. ,vol. 31, pp. 863- 870 ,(1982) , 10.1109/TC.1982.1676101
Leland, Solomon, Dense Trivalent Graphs for Processor Interconnection IEEE Transactions on Computers. ,vol. 31, pp. 219- 222 ,(1982) , 10.1109/TC.1982.1675977
Carlsson, Cruthirds, Sexton, Wright, Interconnection Networks Based on a Generalization of Cube-Connected Cycles IEEE Transactions on Computers. ,vol. 34, pp. 769- 772 ,(1985) , 10.1109/TC.1985.1676627
S Lakshmivarahan, Jung-Sing Jwo, S.K Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey parallel computing. ,vol. 19, pp. 361- 407 ,(1993) , 10.1016/0167-8191(93)90054-O
Shimon Even, R. Endre Tarjan, Network Flow and Testing Graph Connectivity SIAM Journal on Computing. ,vol. 4, pp. 507- 518 ,(1975) , 10.1137/0204043
B.W. Arden, K.W. Tang, Representations and routing for Cayley graphs (computer networks) IEEE Transactions on Communications. ,vol. 39, pp. 1533- 1537 ,(1991) , 10.1109/26.111428
Khaled Day, Anand Tripathi, Arrangement graphs: a class of generalized star graphs Information Processing Letters. ,vol. 42, pp. 235- 241 ,(1992) , 10.1016/0020-0190(92)90030-Y
Q. Ke, S.G. Akl, H. Meijer, On Some Properties and Algorithms for the Star and Pancake Interconnection Networks Journal of Parallel and Distributed Computing. ,vol. 22, pp. 16- 25 ,(1994) , 10.1006/JPDC.1994.1066