Linear time algorithms for finding independent spanning trees on pyramid networks

CCUR > College of Business > Department of Information Management & Graduate Institute of Information Management > periodical articles > Item 987654321/48849

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/48849

Title:	Linear time algorithms for finding independent spanning trees on pyramid networks
Authors:	Wang, SI (Wang, Shuo-, I) Wang, FH (Wang, Fu-Hsing)
Contributors:	資管系
Keywords:	Independent spanning trees Interconnection networks Pyramid networks Graph algorithms
Date:	2020-04
Issue Date:	2020-11-27 15:57:16 (UTC+8)
Abstract:	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.
Relation:	JOURNAL OF COMBINATORIAL OPTIMIZATION 卷冊: 39 期: 3 頁數: 826-848
Appears in Collections:	[Department of Information Management & Graduate Institute of Information Management] periodical articles

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	199	View/Open

View Licence