标题: | 超立方体及局部扭转超立方体之独立扩张树之建造 Constructing independent spanning trees for hypercubes and locally twisted cubes |
作者: | 刘宜君 Liu, Yi-Jiun 陈秋媛 Chen, Chiu-Yuan 应用数学系所 |
关键字: | 资料广播;演算法设计与分析;点独立扩张树;局部扭转超立方体;超立方体;平行演算法;Data broadcasting;Design and analysis of algorithms;Vertex-disjoint spanning trees;Locally twisted cubes;Hypercubes;Parallel algorithm |
公开日期: | 2008 |
摘要: | 在网路中使用多棵独立扩张树对于资料广播有相当多的好处,例如:可以提高容错以及频宽等;因此,在各种的网路结构上,建造多棵独立扩张树,一直以来都被广泛地研究。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. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT079622521 http://hdl.handle.net/11536/42507 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.