完整後設資料紀錄
DC 欄位語言
dc.contributor.author劉宜君en_US
dc.contributor.authorLiu, Yi-Jiunen_US
dc.contributor.author陳秋媛en_US
dc.contributor.authorChen, Chiu-Yuanen_US
dc.date.accessioned2014-12-12T01:30:20Z-
dc.date.available2014-12-12T01:30:20Z-
dc.date.issued2008en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT079622521en_US
dc.identifier.urihttp://hdl.handle.net/11536/42507-
dc.description.abstract在網路中使用多棵獨立擴張樹對於資料廣播有相當多的好處,例如:可以提高容錯以及頻寬等;因此,在各種的網路結構上,建造多棵獨立擴張樹,一直以來都被廣泛地研究。Zehavi和Itai在文獻[26]中,對於建造多棵獨立擴張樹提出了兩個猜測。「點猜測」闡述的是:在一個點連通度為n的圖上,能以圖中任一點為樹根,產生n棵點獨立擴張樹;「邊猜測」闡述的是:在一個邊連通度為n的圖上,能以圖中任一點為樹根,產生n棵邊獨立擴張樹。在文獻[16] 中,Khuller和Schieber證明了點猜測能涵蓋邊猜測。局部扭轉超立方體是超立方體的變形。最近,Hsieh和Tu在文獻[10]中,提出了一個能在n維局部扭轉超立方體上,建造以0為樹根的n棵邊獨立擴張樹的演算法。因為局部扭轉超立方體不具點對稱性質,Hsieh和Tu所提出的演算法無法解決局部扭轉超立方體的邊猜測。在這篇論文中,我們提出了一個可以在局部扭轉超立方體上,以任一點為樹根,建構n棵點獨立擴張樹的演算法;我們的演算法證明了局部扭轉超立方體符合點猜測,當然,也證明了局部扭轉超立方體符合邊猜測。此外,我們的演算法也能在超立方體上得到一樣的結果。zh_TW
dc.description.abstractThe 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.en_US
dc.language.isoen_USen_US
dc.subject資料廣播zh_TW
dc.subject演算法設計與分析zh_TW
dc.subject點獨立擴張樹zh_TW
dc.subject局部扭轉超立方體zh_TW
dc.subject超立方體zh_TW
dc.subject平行演算法zh_TW
dc.subjectData broadcastingen_US
dc.subjectDesign and analysis of algorithmsen_US
dc.subjectVertex-disjoint spanning treesen_US
dc.subjectLocally twisted cubesen_US
dc.subjectHypercubesen_US
dc.subjectParallel algorithmen_US
dc.title超立方體及局部扭轉超立方體之獨立擴張樹之建造zh_TW
dc.titleConstructing independent spanning trees for hypercubes and locally twisted cubesen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
顯示於類別:畢業論文


文件中的檔案:

  1. 252101.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。