| d-子树划分问题 |
| |
| 引用本文： | 蔡延光,章云,钱积新.d-子树划分问题[J].计算机学报,2010,33(4). |
| |
| 作者姓名： | 蔡延光 章云 钱积新 |
| |
| 作者单位： | 1. 广东工业大学自动化学院,广州,510006
2. 浙江大学工业控制技术国家重点实验室,杭州,310027 |
| |
| 基金项目： | 国家自然科学基金(60374062);;广东省自然科学基金团队项目(8351009001000002);;广东省科技计划项目基金(2007B010200070,2008B010200005)资助~~ |
| |
| 摘 要： | 边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.
|
| 关 键 词： | d-子树划分 子树划分 NP-完全 树 算法 复杂度 |
The d-Subtree Partition Problem |
| |
| Affiliation: | Faculty of Automation/a>;Guangdong University of Technology/a>;Guangzhou 510006;National Laboratory of Industrial Control Technology/a>;Zhejiang University/a>;Hangzhou 310027 |
| |
| Abstract: | A d-subtree partition of undirected simple graph with nonnegative edge-weights is a collection of pairwise vertex-disjoint subtrees such that the union of vertex sets of these subtrees is equal to the vertex set of the graph and each subtree has diameter of no more than d,where d is a nonnegative real.The d-subtree partition problem of a graph is to find a d-subtree partition that has the smallest cardinality among all d-subtree partitions of the graph and the cardinality.The d-subtree partition problem has... |
| |
| Keywords: | d-subtree partition subtree partition NP-complete tree algorithm complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
