《计算机学报》文章摘要   全文下载
文章题目	d-子树划分问题
作者	蔡延光1) 章云1) 钱积新2)
作者单位	1)(广东工业大学自动化学院 广州 510006) 2)(浙江大学工业控制技术国家重点实验室 杭州 310027)
发表年份	2010
发表月份	4期(652—665)
文章摘要	摘要 边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数)，如果这些子树的顶点集的并等于此图的顶点集，且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d，边赋非负权二分平面图的d-子树划分问题是NP-完全问题；提出了求解边赋非负权树d-子树划分问题的一个线性时间算法，详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点. 关键词 d-子树划分；子树划分；NP-完全；树；算法；复杂度 中图法分类号 TP301 DOI号 10.3724/SP.J.1016.2010.00652