%0 Journal Article
%T 边赋权森林ω-路划分的O(n)算法
%A 蔡延光
%A 张新政
%A 钱积新
%A 孙优贤
%J 软件学报
%D 2003
%I 
%X ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.
%K 广播
%K 路划分
%K ω-路划分
%K 树
%K 森林
%K 算法
%K 复杂度
%K NP-完全
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=9D9EC71A7BEB5A6C&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=94C357A881DFC066&sid=547650636788ED84&eid=6484E0C1B87D264C&journal_id=1000-9825&journal_name=软件学报&referenced_num=2&reference_num=22