摘要
w-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,w-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的w-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的w-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的w-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.
w-path partition problem is the generalization of path partition problem. It comes of broadcasting communication in parallel computer system, computer network and distributed control system. This problem can be described by graph theory terminology as follows. Let G=(V,E) be an undirected simple graph with nonnegative edge-weights, and w0 be a real. {P1, P2, , Pm} is called to be an w-path partition of G if P1, P2, , Pm are m pairwise vertex-disjoint paths of G such that )()(1GVPVmii==U, and W(Pi)w (for all i=1, 2, , m, where W(Pi)= )()(iPEeew). The w-path partition number of G is the smallest cardinality of w-path partition of G. The w-path partition problem of G is to find a minimum -path partition and the -path partition number of G. It is evident that -path partition problem for any graph is NP-complete by the NP-completeness of Hamiltonian path. In this paper, some properties of -path partition have been investigated for paths, trees and forests with nonnegative edge-weights respectively. Linear time algorithms have been presented to solve -path partition problem for any path and tree with nonnegative edge-weights respectively. Local realization techniques and complexities of these two algorithms have been discussed in detail. Based above algorithms, an O(n) algorithm has been designed to solve -path partition problems for forests with nonnegative edge-weights. The algorithms presented in this paper are concise, and require less time and space.
出处
《软件学报》
EI
CSCD
北大核心
2003年第5期897-903,共7页
Journal of Software
基金
广东省自然科学基金
广东省科技攻关项目~~
