%0 Journal Article
%T 边赋权森林ω-路划分的O(n)算法
%A 孙优贤
%A 张新政
%A 蔡延光
%A 钱积新
%J -
%D 2003
%X ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间
%K 广播 路划分 ω-路划分 树 森林 算法 复杂度 NP-完全
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=20030505&flag=1