边赋权森林ω-路划分的O(n)算法
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
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2002-03-28
  • 最后修改日期:2002-07-08
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号