- 期刊
- OpenAccess
Optimal Independent Spanning Trees on Hypercubes
並列摘要
Two spanning trees rooted at some vertex r in a graph G are said to be independent if for each vertex v of G, v≠r, the paths from r to v in two trees are vertex-disjoint. A set of spanning trees of G is said to be independent if they are pairwise independent. A set of independent spanning trees is optimal if the average path length of the trees is the minimum. Any k-dimensional hypercube has k independent spanning trees rooted at an arbitrary vertex. In this paper, an O(kn) time algorithm is proposed to construct k optimal independent spanning trees on a k-dimensional hypercube, where n=2(superscript k) is the number of vertices in a hypercube.
被引用紀錄
Wang, Z. H. (2008). 利用肝素化的纖維素基質吸附第二型重組腺病毒並進行局部基因傳導 [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2008.00192
延伸閱讀
- Tang, S. M. (2019). How Many Optimal Independent Spanning Trees are there in a Hypercube. In 國立金門大學 (Ed.), NCS 2019 全國計算機會議 (pp. 110-113). 國立金門大學. https://doi.org/10.6927/NCS.201911.0022
- Liu, Y. J. (2009). Constructing independent spanning trees for hypercubes and locally twisted cubes [master's thesis, National Chiao Tung University]. Airiti Library. https://doi.org/10.6842/NCTU.2009.00399
- Yang, Y. X. (2020). Constructing Completely Independent Spanning Trees in Balanced Hypercubes [master's thesis, National Taipei University of Business]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0064-0305202311150216
- Chang, H. Y., & Chen, R. J. (2000). Incrementally Extensible Folded Hypercube Graphs. Journal of Information Science and Engineering, 16(2), 291-300. https://doi.org/10.6688/JISE.2000.16.2.5
- Kao, S. S., Chang, J. M., & Pai, K. J. (2018). Independent Spanning Trees on Bubble-Sort Networks. In 國立東華大學 (Ed.), NCS 2017 全國計算機會議 (pp. 232-236). 國立東華大學. https://doi.org/10.29428/9789860544169.201801.0044