d-子树划分问题

作者：蔡延光; 章云; 钱积新

来源：计算机学报, 2010, (04): 652-665.

• d-子树划分
• 子树划分
• NP-完全
• 树
• 算法
• 复杂度 d-subtree partition
• subtree partition
• NP-complete
• tree
• algorithm
• complexity

边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.

• 单位
  浙江大学; 工业控制技术国家重点实验室; 广东工业大学