超立方體及局部扭轉超立方體之獨立擴張樹之建造

Constructing independent spanning trees for hypercubes and locally twisted cubes

劉宜君(Yi-Jiun Liu)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00399

摘要

在網路中使用多棵獨立擴張樹對於資料廣播有相當多的好處，例如：可以提高容錯以及頻寬等；因此，在各種的網路結構上，建造多棵獨立擴張樹，一直以來都被廣泛地研究。Zehavi和Itai在文獻[26]中，對於建造多棵獨立擴張樹提出了兩個猜測。「點猜測」闡述的是：在一個點連通度為n的圖上，能以圖中任一點為樹根，產生n棵點獨立擴張樹；「邊猜測」闡述的是：在一個邊連通度為n的圖上，能以圖中任一點為樹根，產生n棵邊獨立擴張樹。在文獻[16] 中，Khuller和Schieber證明了點猜測能涵蓋邊猜測。局部扭轉超立方體是超立方體的變形。最近，Hsieh和Tu在文獻[10]中，提出了一個能在n維局部扭轉超立方體上，建造以0為樹根的n棵邊獨立擴張樹的演算法。因為局部扭轉超立方體不具點對稱性質，Hsieh和Tu所提出的演算法無法解決局部扭轉超立方體的邊猜測。在這篇論文中，我們提出了一個可以在局部扭轉超立方體上，以任一點為樹根，建構n棵點獨立擴張樹的演算法；我們的演算法證明了局部扭轉超立方體符合點猜測，當然，也證明了局部扭轉超立方體符合邊猜測。此外，我們的演算法也能在超立方體上得到一樣的結果。

關鍵字

資料廣播 ； 演算法設計與分析 ； 點獨立擴張樹 ； 局部扭轉超立方體 ； 超立方體 ； 平行演算法

並列摘要

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages such as the increase of fault-tolerance and bandwidth. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. In [27], Zehavi and Itai stated two versions of the n independent spanning trees 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. In [16], Khuller and Schieber proved that the vertex conjecture implies the edge conjecture. Recently, in [12], Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for an n-dimensional locally twisted cube, which is a variant of the hypercube. Since the locally twisted cube is it not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for the locally twisted cube. In the thesis, we confirm the vertex conjecture (and hence also the edge conjecture) for the locally twisted cube by proposing an algorithm to construct $n$ vertex-ISTs rooted at any vertex for the n-dimensional locally twisted cube. We also confirm the vertex conjecture (and hence also the edge conjecture) for the hypercube.

並列關鍵字

Data broadcasting ； Design and analysis of algorithms ； Vertex-disjoint spanning trees ； Locally twisted cubes ； Hypercubes ； Parallel algorithm

參考文獻

[2] F. Bao , Y. Igarashi and S. R. Ohring, “Reliable broadcasting in product networks," Graph-theoretic Concepts in Computer Science, vol. 1517, pp. 310-323, 1998.

[3] Y. S. Chen, C. Y. Chiang and C.Y. Chen,“Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy," Journal of System Architecyure, vol. 50, pp. 575-589, 2004.

[5] S. Curran, O. Lee and X. Yu,“Finding four independent trees," SIAM Journal on Computing, vol. 35, pp. 1023-1058, 2006.

[6] J. Cheriyan and S.N. Maheshwari, “Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs," Journal of Algorithms, vol. 9, pp.

[8] Z. Ge and S. L. Hakimi, “Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs," SIAM Journal on Computing, vol. 26, pp. 79-92, 1997.