| 本文已被：浏览 4907次 下载 5922次 |
码上扫一扫！ |
|
|
| 边赋权森林ω-路划分的O(n)算法 |
|
蔡延光1, 张新政1, 钱积新2, 孙优贤2
|
|
1.广东工业大学,自动化学院,广东,广州,510090;2.浙江大学,工业控制技术国家重点实验室,浙江,杭州,310027
|
|
| 摘要: |
| ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间. |
| 关键词: 广播 路划分 ω-路划分 树 森林 算法 复杂度 NP-完全 |
| DOI： |
| 分类号: |
| 基金项目: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 (广东省科技攻关项目) |
|
| An O(n) Algorithm for ω-Path Partition of Edge-Weighted Forests |
|
CAI Yan-Guang,ZHANG Xin-Zheng,QIAN Ji-Xin,SUN You-Xian
|
| 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. |
| Key words: broadcasting path partition ω-path partition tree forest algorithm complexity NP-complete |
