One-to-one disjoint path covers on alternating group graphs

Lantao You; Jianxi Fan; Yuejuan Han; Xiaohua Jia

doi:10.1016/j.tcs.2014.09.041

One-to-one disjoint path covers on alternating group graphs

Lantao You, Jianxi Fan^*, Yuejuan Han, Xiaohua Jia

^*Corresponding author for this work

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

21 Citations (Scopus)

Abstract

The alternating group graph, denoted by AG_n, is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes μ and ν, there exist m node-disjoint paths for any integer n≥3 with 1≤m≤2n-4 whose union covers all the nodes of AG_n. For any node of AG_n has exactly 2n-4 neighbors, 2n-4 is the maximum number of node-disjoint paths can be constructed in AG_n.

Original language	English
Pages (from-to)	146-164
Journal	Theoretical Computer Science
Volume	562
Issue number	C
DOIs	https://doi.org/10.1016/j.tcs.2014.09.041
Publication status	Published - 2015

Research Keywords

Alternating group graph
Interconnection network
One-to-one disjoint path covers
Parallel computing

Access Output

10.1016/j.tcs.2014.09.041Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{7f5b228502da4919a5be9f0c3fed50cd,

title = "One-to-one disjoint path covers on alternating group graphs",

abstract = "The alternating group graph, denoted by AGn, is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes μ and ν, there exist m node-disjoint paths for any integer n≥3 with 1≤m≤2n-4 whose union covers all the nodes of AGn. For any node of AGn has exactly 2n-4 neighbors, 2n-4 is the maximum number of node-disjoint paths can be constructed in AGn.",

keywords = "Alternating group graph, Interconnection network, One-to-one disjoint path covers, Parallel computing",

author = "Lantao You and Jianxi Fan and Yuejuan Han and Xiaohua Jia",

year = "2015",

doi = "10.1016/j.tcs.2014.09.041",

language = "English",

volume = "562",

pages = "146--164",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - One-to-one disjoint path covers on alternating group graphs

AU - You, Lantao

AU - Fan, Jianxi

AU - Han, Yuejuan

AU - Jia, Xiaohua

PY - 2015

Y1 - 2015

N2 - The alternating group graph, denoted by AGn, is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes μ and ν, there exist m node-disjoint paths for any integer n≥3 with 1≤m≤2n-4 whose union covers all the nodes of AGn. For any node of AGn has exactly 2n-4 neighbors, 2n-4 is the maximum number of node-disjoint paths can be constructed in AGn.

AB - The alternating group graph, denoted by AGn, is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes μ and ν, there exist m node-disjoint paths for any integer n≥3 with 1≤m≤2n-4 whose union covers all the nodes of AGn. For any node of AGn has exactly 2n-4 neighbors, 2n-4 is the maximum number of node-disjoint paths can be constructed in AGn.

KW - Alternating group graph

KW - Interconnection network

KW - One-to-one disjoint path covers

KW - Parallel computing

UR - http://www.scopus.com/inward/record.url?scp=84926311954&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84926311954&origin=recordpage

U2 - 10.1016/j.tcs.2014.09.041

DO - 10.1016/j.tcs.2014.09.041

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 562

SP - 146

EP - 164

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

One-to-one disjoint path covers on alternating group graphs

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this