Constructing independent spanning trees for hypercubes and locally twisted cubes
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
22 | en_US |
dc.citation.spage |
17 | en_US |
dc.contributor.author |
Liu, Yi-Jiun | en_US |
dc.contributor.author |
Chou, Well Y. | en_US |
dc.contributor.author |
Lan, James K. | 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:20:22Z | |
dc.date.available |
2014-12-08T15:20:22Z | |
dc.date.issued |
2009 | en_US |
dc.description.abstract |
Multiple independent spanning trees (ISTs) have applications to fault-tolerant and data broadcasting in interconnections. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. There are two versions of the n ISTs conjecture. The vertex (edge,) conjecture is that any n-connected (n-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. Note that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQ(n)), which is a variant of the n-dimensional hypercube (Q(n)). Since LTQ(n) is not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for LTQ(n). In the paper we confirm the vertex conjecture (and hence also the edge conjecture) for LTQ(n) by proposing an algorithm to construct n vertex-ISTs rooted at any vertex. We also confirm the vertex (and also the edge) conjecture for Q(n). To the best of our knowledge, our algorithm is the first algorithm that can construct n vertex-ISTs rooted at any vertex for both LTQ(n) and Q(n). | en_US |
dc.identifier.isbn |
978-1-4244-5403-7 | en_US |
dc.identifier.journal |
2009 10TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS, AND NETWORKS (ISPAN 2009) | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/14479 | |
dc.identifier.wosnumber |
WOS:000291013200004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Data broadcasting | en_US |
dc.subject |
Design and analysis of algorithms | en_US |
dc.subject |
Vertex-disjoint spanning trees | en_US |
dc.subject |
Locally twisted cubes | en_US |
dc.subject |
Hypercubes | en_US |
dc.subject |
Parallel algorithm | en_US |
dc.title |
Constructing independent spanning trees for hypercubes and locally twisted cubes | en_US |
dc.type |
Article | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 會議論文
引用此條目
Liu, Y.-J., Chou, W. Y., Lan, J. K., & Chen, C. (2009). Constructing independent spanning trees for hypercubes and locally twisted cubes. 2009 10TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS, AND NETWORKS (ISPAN 2009), 17–22. https://ir.lib.nycu.edu.tw/handle/11536/14479
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/14479