Hamiltonian path embeddings in conditional faulty k-ary n-cubes

被引：12

作者：

Wang, Shiying ^{[1
,2
]}

Zhang, Shurong ^{[2
]}

Yang, Yuxing ^{[1
]}

机构：

[1] Henan Normal Univ, Coll Math & Informat Sci, Xinxiang 453007, Henan, Peoples R China

[2] Shanxi Univ, Sch Math Sci, Taiyuan 030006, Shanxi, Peoples R China

来源：

INFORMATION SCIENCES | 2014年 / 268卷

基金：

中国国家自然科学基金; 国家教育部博士点专项基金资助;

关键词：

Interconnection network; Path embedding; Hamiltonian path; Conditional edge fault; k-Ary n-cube; COVERS; PANCYCLICITY; NETWORKS; GRAPHS; CYCLES;

D O I：

10.1016/j.ins.2014.01.044

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. In this paper, we consider the faulty k-ary n-cube with even k 4 and n 2 such that each vertex of the k-ary n-cube is incident with at least two healthy edges. Based on this requirement, we prove that the k-ary n-cube contains a hamiltonian path joining every pair of vertices which are in different parts, even if it has up to 4n - 5 edge faults and this result is optimal. (c) 2014 Elsevier Inc. All rights reserved.

引用

页码：463 / 488

页数：26

共 25 条

[1] Blue Gene/L torus interconnection network [J].

Adiga, NR ;

Blumrich, MA ;

Chen, D ;

Coteus, P ;

Gara, A ;

Giampapa, ME ;

Heidelberger, P ;

Singh, S ;

Steinmacher-Burow, BD ;

Takken, T ;

Tsao, M ;

Vranas, P .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 2005, 49 (2-3) :265-276

[2] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[3]

[Anonymous], IEEE MICRO

[4]

[Anonymous], 2007, GRAPH THEORY

[5]

[Anonymous], P 38 IEEE COMP SOC I

[6]

Ashir Y. A., 1997, Parallel Processing Letters, V7, P49, DOI 10.1142/S0129626497000073

[7] Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes [J].

Ashir, YA ;

Stewart, IA .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (03) :317-328

[8] Paired many-to-many disjoint path covers of the hypercubes [J].

Chen, Xie-Bin .

INFORMATION SCIENCES, 2013, 236 :218-223

[9] Panconnectivity and Edge-Pancyclicity of k-Ary n-Cubes [J].

Hsieh, Sun-Yuan ;

Lin, Tsong-Jie .

NETWORKS, 2009, 54 (01) :1-11

[10] Fault-free Hamiltonian cycles in faulty arrangement graphs [J].

Hsieh, SY ;

Chen, GH ;

Ho, CW .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) :223-237

← 1 2 3 →