標題: Maximally Local Connectivity on Augmented Cubes 作者: Chen, Y-ChuangChen, Meng-HungTan, Jimmy J. M.資訊工程學系Department of Computer Science 關鍵字: connectivity;local connectivity;fault tolerance;vertex-disjoint path;augmented cube 公開日期: 2009 摘要: Connectivity is all important measurement for the fault tolerance in interconnection networks. It is known that the augmented cube AQ(n) is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classical Menger\'s Theorem, every pair of vertices in AQ(n) is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by some research works on networks with faults, we have a further result that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ(n) - F is connected by min{deg(f)(u), deg(f)(v)} vertex-disjoint fault-free paths, where deg(f)(u) and deg(f)(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we have another result that for ally faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 4n - 9 for n >= 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar - 1 vertices in AQ(n) - F. In general, a remaining large fault-free connected component also increases fault tolerance. URI: http://hdl.handle.net/11536/134409 ISBN: 978-3-642-03094-9 ISSN: 0302-9743 期刊: ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, PROCEEDINGS Volume: 5574 起始頁: 121 結束頁: + Appears in Collections: Conferences Paper