广东工业大学学报 ›› 2010, Vol. 27 ›› Issue (3): 35-40.

• 综合研究 • 上一篇    下一篇

星图上基于循环置换的任意两点之间的最短路径算法

  

  1. 广东工业大学应用数学学院，广东广州510006
  • 出版日期:2010-09-25 发布日期:2010-09-25
  • 作者简介:王静(1985-)，女，硕士研究生，主要研究方向为组合数学与最优化

The Shortest Path Algorithm Between Two Arbitrary Nodes Based on Cycle Permutation in the Star Graph

  1. Faculty of Applied Mathematics，Guangdong University of Technology，Guangzhou 510006，China
  • Online:2010-09-25 Published:2010-09-25

HTML

PDF (PC)

2489

摘要： 针对路由选择对网络性能起重要作用，提出了星图上任意两点之间的最短路径算法．运用群论的循环置换的性质证明了两点之间的距离公式，给出了两点之间所有最短路径个数的一般代数表达式．

关键词: 星图；最短路径；循环置换；距离

Abstract: For the routing plays an important role in the performance of the network，the shortest path algorithm between two arbitrary nodes in the star graph is proposed．The distance form ula between two points is proved by using the nature of the cycle perm utation of the Group Th eory，and the general algebraic expression for the number of all the shortest paths between two nodes is provided．

Key words: the star graph；the shortest path；cycle perm utation；the distance

[1]Day Khaled，Tripa~i Anand．A Comparative Study of Topoiogical Properties of Hypercubes and Star Graphs[J]．IEEE Transactions on Parallel and Distributed Systems，1994，5(1)：31-38．

[2]Akers S B，Harel D，Krishnamurthy B．The star graph：An attractive alternative to the n-cube[C]∥Proc Int Conf．New York：Parallel Processing，1987：393-400．

[3]Chen Chi-Chang，Chen Jianer．Vertex-Disjoint Routings in Star Graphs[J]．IEEE Algorithms and Architectures for Parallel Processing，1995，1：460-464．

[4]Yeh Sheng-I，Yang Chang-Biau，Chen Hon-Chan．Fault—Tolerant Routing on the Star Graph with Safety Vectors[J]．IEEE Parallel Architectures，Algorithms and Networks，2002(5)：266-271．

[5]唐高华．近世代数[M]．北京：清华大学出版社，2008．

[6]徐俊明．组合网络[M]．北京：科学出版社，2007
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发