- 會議論文
- OpenAccess
Independent Spanning Trees on Bubble-Sort Networks
摘要
A set of spanning trees in a graph G is called independent spanning trees (ISTs for short) if they are rooted at the same vertex, say r, and for each vertex v(≠ r) in G, the two paths from v to r in any two trees share no common vertex except for the two end vertices v and r (i.e., the two paths are internally vertex-disjoint). The n-dimensional bubble- sort network B_n is one of the most attractive interconnection networks for multiprocessor systems. In this paper, we present an algorithm to construct n - 1 ISTs rooted at the identity vertex of B_n. Since B_n is vertex transitive, we can easily derive a set of n - 1 ISTs with the common root at any other vertex of B_n. Also, since B_n is a regular graph with connectivity n - 1, the number of constructed ISTs reaches the upper limit.
延伸閱讀
- 蔡宏偉（2014）。Listing All Minimum Spanning Trees in an Undirected Graph Using MapRedcue〔碩士論文，國立臺北商業大學〕。華藝線上圖書館。https://doi.org/10.6818/NTUB.2014.00007
- 林高正、曾文宏、鄧凱年、許惠馨（2019）。Solving Possibilistic Minimum Spanning Tree Problems by Using Expected Value Models。管理資訊計算，8()，37-50。https://doi.org/10.6285/MIC.201908/SP_02_8.0004
- 盧威龍（2008）。Upper Bounds on Perfect Embedding Binary trees to Hypercubes〔碩士論文，國立暨南國際大學〕。華藝線上圖書館。https://doi.org/10.6837/NCNU.2008.00224
- Tamura, S., Nishitani, Y., Hosokawa, C., Miyoshi, T., Sawai, H., Kamimura, T., Yagi, Y., Matsumoto, Y. M., & Chen, Y. W. (2016). Spike Code Flow in Cultured Neuronal Networks. Computational Intelligence and Neuroscience, 2016(), 478-488. https://doi.org/10.1155/2016/7267691
- 李政緯（2014）。Approximation Algorithms for Directed Steiner Tree Problem in Graphs with Sparse Splitting Nodes〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-2912201413553988