边赋权森林ω-路划分的O(n)算法

• 作者: 孙优贤 张新政 蔡延光 钱积新
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 广播 路划分 ω-路划分 树 森林 算法 复杂度 NP-完全
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 897-903
• 页数: 7页
• 分类号: TP301
• 字数: 7511字
• 语种: 中文

摘要

ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张新政	广东工业大学自动化学院	81	660	13.0	22.0
2	钱积新	浙江大学工业控制技术国家重点实验室	164	3326	26.0	51.0
3	孙优贤	浙江大学工业控制技术国家重点实验室	231	5136	33.0	62.0
4	蔡延光	广东工业大学自动化学院	181	812	14.0	20.0