###
DOI:
Journal of Software:2003.14(5):897-903

边赋权森林ω-路划分的O(n)算法
蔡延光,张新政,钱积新,孙优贤
(广东工业大学,自动化学院,广东,广州,510090;浙江大学,工业控制技术国家重点实验室,浙江,杭州,310027)
An O(n) Algorithm for ω-Path Partition of Edge-Weighted Forests
CAI Yan-Guang,ZHANG Xin-Zheng,QIAN Ji-Xin,SUN You-Xian
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3010   Download 2730
Received:March 28, 2002    Revised:July 08, 2002
> 中文摘要: ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.
中文关键词: 广播  路划分  ω-路划分    森林  算法  复杂度  NP-完全
Abstract:ω-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 ω≥0 be a real. {P1, P2, …, Pm} is called to be an ω-path partition of G if P1, P2, …, Pm are m pairwise vertex-disjoint paths of G such that , and V(P)()(1GVPVmii==Ui)≤ω (for all i=1, 2, …, m, where W(Pi)= ). The ω-path partition number of G is the smallest cardinality of ω-path partition of G. The ω-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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the Natural Science Foundation of Guangdong Province of China under Grant No.010060 (广东省自然科学基金); the Key Science-Technology Project of Guangdong Province of China under Grant No.C31801 (广东省科技攻关项目) Supported by the Natural Science Foundation of Guangdong Province of China under Grant No.010060 (广东省自然科学基金); the Key Science-Technology Project of Guangdong Province of China under Grant No.C31801 (广东省科技攻关项目)
Foundation items:
Reference text:

蔡延光,张新政,钱积新,孙优贤.边赋权森林ω-路划分的O(n)算法.软件学报,2003,14(5):897-903

CAI Yan-Guang,ZHANG Xin-Zheng,QIAN Ji-Xin,SUN You-Xian.An O(n) Algorithm for ω-Path Partition of Edge-Weighted Forests.Journal of Software,2003,14(5):897-903