对换网络的可系性（英文）

乔宏伟; 艾尔肯·吾买尔

doi:10.13568/j.cnki.651094.2017.01.008

您当前的位置：

首页 >

文章列表页 >

对换网络的可系性（英文）

数理科学 | 更新时间：2026-01-21

- 对换网络的可系性（英文）
- 对换网络的可系性（英文）
- 新疆大学学报（自然科学版中英文） 2017年34卷第1期页码：40-43
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  supported by the National Natural Science Foundation of China(11361060)
- DOI：10.13568/j.cnki.651094.2017.01.008
  中图分类号： O157.5
- 纸质出版：2017
- 稿件说明：
移动端阅览
[1]乔宏伟,艾尔肯·吾买尔.对换网络的可系性（英文）[J].新疆大学学报(自然科学版),2017,34(01):40-43.
[1]乔宏伟,艾尔肯·吾买尔.对换网络的可系性（英文）[J].新疆大学学报(自然科学版),2017,34(01):40-43. DOI： 10.13568/j.cnki.651094.2017.01.008.

DOI：10.13568/j.cnki.651094.2017.01.008.

摘要

G是一个图

k是一个正整数

v是G中任意两个不相同的点

u与v之间的一个k-container C(u

v)指的是从u到v的k条内部点不交的路的集合.并且C(u

v)被称作是k*-container

如果它包含G中所有的点.图G是k*连通的(或者说k生成连通的)

如果对于G中任意两个不同的点u

v都存在u到v的一个k*-container.一个二部图G是k*可系的

如果对于来自不同部分的任意两个点u

v都存在u到v的一个k*-container.在这篇文章中我们证明了n阶对换网络TNn是(C2n)*可系的.

Abstract

For a graph G and an integer k > 0 and for u

v ∈ G with u v

a k-container C(u

v) of G is a set of k internally disjoint(u

v)-paths

and C(u

v) is called a k*-container if it contains all vertices of G. A graph G is k*-connected(or spanning k-connected) if for any u

v ∈ V(G) with u v

G has a k*-container between u and v. A bipartite graph G is k*-laceable if for any u

v from different partite sets of G

there is a k*-container C(u

v). In this paper

we prove that the n-dimensional transposition network T Nnis(C2n)*-laceable.

关键词

Keywords

references

Leighton F T.Introductions to Parallel Algorithms and Architectures:Arrays,Trees and Hypercubes[M].San Manteo:Morgan Kaufman,1992.

Lakshmivarahan S,Jwo J S,Dhall S K.Symmetry in interconnection networks based on Caley graphs of permutation groups:a survey[J].Parallel Comput,1993,19:361-407.

Chase P J.Transposition graphs[J].SIAM J Comput,1973,2:128-133.

Skiena S.Implementing Discrete Mathematics:Combinatorics and Graph Theory with Methematica[M].Redwood City:Addison-Wesley,1990.

Akers A B,Krishnamurthy B.A group-theoretic model for symmetric interconnection networks[J].IEEE Trans Comput,1989,38:555-565.

Fujita S.Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs[J].Networks,2010,56:149-157.

Latifi S,Srimani P K.Transposition networks as a class of fault-tolerant robust networks[J].IEEE Trans Comput,1996,45:230-238.

Suzuki Y,Kaneko K,Nakamori M.Node-disjoint paths algorithm in a transposition graph[J].IEICE Trans Inf Syst,2006,E89-D:2600-2605.

Hung R-W.The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks[J].Discrete Appl Math,2015,181:109-122.

Hussak W.Disjoint Hamilton cycles in transposition graphs[J].Discrete Appl Math,2016,206:56-64.

Ganesan A.Automorphism group of the complete transposition graph[J].J Algebr Comb,2015,42(3):793-801.

Kalpakis K,Yesha Y.On the bisection width of the transposition network[J].Networks,1997,29:69-76.

Bondy J A,Murty U S R.Graph Theory[M].New York:Springer,2008.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据