Constructing independent spanning trees for locally twisted cubes
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
2252 | en_US |
dc.citation.issue |
22 | en_US |
dc.citation.spage |
2237 | en_US |
dc.citation.volume |
412 | en_US |
dc.citation.woscount |
14 | |
dc.contributor.author |
Liu, Yi-Jiun | en_US |
dc.contributor.author |
Lan, James K. | en_US |
dc.contributor.author |
Chou, Well Y. | en_US |
dc.contributor.author |
Chen, Chiuyuan | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:11:33Z | |
dc.date.available |
2014-12-08T15:11:33Z | |
dc.date.issued |
2011-05-13 | en_US |
dc.description.abstract |
The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4; therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n); consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.tcs.2010.12.061 | 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.2010.12.061 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/8862 | |
dc.identifier.wosnumber |
WOS:000289930300002 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Independent spanning trees | en_US |
dc.subject |
Data broadcasting | en_US |
dc.subject |
Design and analysis of algorithms | en_US |
dc.subject |
Locally twisted cubes | en_US |
dc.subject |
Hypercubes | en_US |
dc.subject |
Hypercube variants | en_US |
dc.subject |
Parallel algorithm | en_US |
dc.title |
Constructing independent spanning trees for locally twisted cubes | en_US |
dc.type |
Article | en_US |
檔案
- 000289930300002.pdf (460.8 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Liu, Y.-J., Lan, J. K., Chou, W. Y., & Chen, C. (2011). Constructing independent spanning trees for locally twisted cubes. THEORETICAL COMPUTER SCIENCE, 412(22), 2237–2252. https://doi.org/10.1016/j.tcs.2010.12.061
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/8862