| 边赋权森林ω-路划分的O(n)算法 |
| |
| 作者姓名： | 蔡延光 张新政 钱积新 孙优贤 |
| |
| 作者单位： | 广东工业大学,自动化学院,广东,广州,510090;广东工业大学,自动化学院,广东,广州,510090;浙江大学,工业控制技术国家重点实验室,浙江,杭州,310027;浙江大学,工业控制技术国家重点实验室,浙江,杭州,310027 |
| |
| 基金项目： | 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 (广东省科技攻关项目) |
| |
| 摘 要： | ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.
|
| 关 键 词： | 广播 路划分 ω-路划分 树 森林 算法 复杂度 NP-完全 |
| 文章编号： | 1000-9825/2003/14(05)0897 |
| 收稿时间： | 2002-03-28 |
| 修稿时间： | 2002-07-08 |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
