Embedding k(n−k) edge-disjoint spanning trees in arrangement graphs |
| |
Authors: | Chin-Tsai Lin |
| |
Affiliation: | Department of Information Management, Kun-Shan University of Technology, 949 Da Wan Rd., Yung-Kang City, Tainan Hsien 710, Taiwan, ROC |
| |
Abstract: | The arrangement graphs are a class of generalized star graphs. In this paper we construct a graph that consists of the maximum number of directed edge-disjoint spanning trees in an arrangement graph. The paths that connect the common root node to any given node through different spanning trees are node-disjoint, and the lengths of these paths differ from the shortest possible lengths by a small additive constant. This graph can be used to derive fault-tolerant algorithms for broadcasting and scattering problems without prior knowledge of the faulty elements of the network. |
| |
Keywords: | Edge-disjoint spanning trees Node-disjoint paths Alternating group graphs Arrangement graphs Fault tolerance |
本文献已被 ScienceDirect 等数据库收录! |
|