One-to-one disjoint path covers on k-ary n-cubes
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
4530 | en_US |
dc.citation.issue |
35 | en_US |
dc.citation.spage |
4513 | en_US |
dc.citation.volume |
412 | en_US |
dc.citation.woscount |
9 | |
dc.contributor.author |
Shih, Yuan-Kang | en_US |
dc.contributor.author |
Kao, Shin-Shin | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:28:05Z | |
dc.date.available |
2014-12-08T15:28:05Z | |
dc.date.issued |
2011-08-12 | en_US |
dc.description.abstract |
The k-ary n-cube, Q(n)(k) is one of the most popular interconnection networks. Let n >= 2 and k >= 3. It is known that Q(n)(k) is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {P(i) vertical bar 0 <= i <= r - 1} between any two distinct vertices u and v of Q(n)(k) when k is odd, and there exist r vertex disjoint paths {R(i) vertical bar 0 <= i <= r - 1} between any pair of vertices to and b from different partite sets of Q(n)(k) when k is even, such that boolean OR(r-1)(i=0) P(i) or boolean OR(r-1)(i=0) R(i) covers all vertices of Q(n)(k) for 1 <= r <= 2n. In other words, we construct the one-to-one r-disjoint path cover of Q(n)(k) for any r with 1 <= r <= 2n. The result is optimal since any vertex in Q(n)(k) has exactly 2n neighbors. (C) 2011 Elsevier B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.tcs.2011.04.035 | en_US |
dc.identifier.issn |
0304-3975 | en_US |
dc.identifier.journal |
THEORETICAL COMPUTER SCIENCE | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.tcs.2011.04.035 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/20343 | |
dc.identifier.wosnumber |
WOS:000294031200006 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Hypercube | en_US |
dc.subject |
k-ary n-cube | en_US |
dc.subject |
Hamiltonian | en_US |
dc.subject |
Disjoint path cover | en_US |
dc.title |
One-to-one disjoint path covers on k-ary n-cubes | en_US |
dc.type |
Article | en_US |
檔案
- 000294031200006.pdf (1.21 MB, Adobe PDF)
所屬典藏: 期刊論文