d-子树划分问题  

The d-Subtree Partition Problem

作　　者：蔡延光[1] 章云[1] 钱积新[2] 

机构地区：[1]广东工业大学自动化学院,广州510006 [2]浙江大学工业控制技术国家重点实验室,杭州310027

出　　处：《计算机学报》2010年第4期652-665,共14页Chinese Journal of Computers

基　　金：国家自然科学基金(60374062);广东省自然科学基金团队项目(8351009001000002);广东省科技计划项目基金(2007B010200070;2008B010200005)资助~~

摘　　要：边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.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 found some applications in operation management,maintenance and test of network such as wire communication network,road traffic network,urban water supply network and power transmission network.In this paper,it is proved that the d-subtree partition problem is NP-complete for bipartite planar graphs with nonnegative edge-weights for any positive real d.A linear time algorithm is presented to solve the d-subtree partition problem for trees with nonnegative edge-weights.Realization strategies for the algorithm are discussed in detail.The algorithm presented can be realized easily and requires less time.

关 键 词：d-子树划分 子树划分 NP-完全 树 算法 复杂度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]