标题: | 增强立方体之最大区域连通性质 Maximally Local Connectivity on Augmented Cubes |
作者: | 陈孟宏 Meng-Hung Chen 谭建民 Jimmy J. M. Tan 资讯科学与工程研究所 |
关键字: | 连通性;最大连通单元;点不相交路径;增强立方体;connectivity;maximal connected component;vertex-disjoint path;augmented cube |
公开日期: | 2007 |
摘要: | 连通性在连结网路中是很重要的问题。Choudum和Sunitha在2002年时提出了增强立方体AQn并指出增强立方体具有以下性质: (1)当n>=4时,对AQn中任意坏点所成的集合F而言,若坏点个数总和不超过2n-2,则AQn-F为一包含2n-|F|个点的连通单元。(2)当n>=4时,AQn中任意两点u和v之间,存在2n-1条点不相交路径。在本篇论文中,我们提供了更进一步的结果,包括 (1)当n>=4时,对AQn中任意坏点所成的集合F而言,若坏点个数总和不超过4n-9,则AQn-F中的最大连通单元至少有2n-|F|-1个点。(2)当n>=4时,对AQn中任意坏点所成的集合F而言,若坏点个数总和不超过2n-7时,则对于AQn中任意两个非坏点u和v之间,存在min{degf(u),degf(v)}条点不相交且无坏点路径。 Connectivity is an important issue in interconnection networks. In 2002, Choudum and Sunitha proposed the augmented cube AQn and indicated that it has the following properties: (1) for any faulty vertex set F and |F|<= 2n-2 for n>=4, AQn-F is a connected component with 2n-|F| vertices; and (2) for any two vertices u and v of AQn with n>=4, there are 2n-1 vertex-disjoint paths joining u and v. In this paper, we show some further results about (1) for any faulty vertex set F and |F|<=4n-9 for n>=4, the maximal connected component of AQn-F has at least 2n-|F|-1 vertices; and (2) for any faulty vertex set F and |F|<=2n-7 for n>=4, each pair of non-faulty vertices u and v in AQn-F is connected by min{degf(u),degf(v)} vertex-disjoint fault-free paths. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT009555509 http://hdl.handle.net/11536/39463 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.