期刊
INFORMATION PROCESSING LETTERS
卷 111, 期 5, 页码 235-238出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2010.11.018
关键词
Independent spanning trees; Fault-tolerant broadcasting; Parallel algorithms; Cartesian product; Generalized base-b hypercube
资金
- NSF of Fujian Province in China [2010J01354]
A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover. the proof of its correctness is simpler than that of Yang et al. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据