Linear time algorithms for finding independent spanning trees on pyramid networks

文化大學機構典藏 CCUR > 商學院 > 資訊管理學系暨資訊管理研究所 > 期刊論文 > Item 987654321/48849

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://irlib.pccu.edu.tw/handle/987654321/48849

题名:	Linear time algorithms for finding independent spanning trees on pyramid networks
作者:	Wang, SI (Wang, Shuo-, I) Wang, FH (Wang, Fu-Hsing)
贡献者:	資管系
关键词:	Independent spanning trees Interconnection networks Pyramid networks Graph algorithms
日期:	2020-04
上传时间:	2020-11-27 15:57:16 (UTC+8)
摘要:	The use of independent spanning trees (ISTs) has scientific applications in fault-tolerant requirement in network protocols and secure message distributions. Most of the designs of ISTs are for those interconnection networks with vertex symmetric property, implying that one can find ISTs rooted on a designated vertex, and, by the vertex symmetry property of the given network, hence have solved the ISTs problem on any arbitrary vertex. The existence of asymmetry makes the ISTs problem even harder than its symmetric counterpart. Cheriyan and Maheshwari (J Algorithms 9:507-537, 1988) showed that, for any 3-connected graph, 3-ISTs rooted at any vertex can be found in O(\|V\|\|E\|) time. In this paper, we propose linear time algorithms that solved 3-ISTs rooted at an arbitrary vertex of pyramid networks.
關聯:	JOURNAL OF COMBINATORIAL OPTIMIZATION 卷冊: 39 期: 3 頁數: 826-848
显示于类别:	[資訊管理學系暨資訊管理研究所 ] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	199	检视/开启

检视Licence

在CCUR中所有的数据项都受到原著作权保护.