赋权树状网络中r-控制集问题和k-中心问题  

r-Dominating Set Problem and k-Center Problem in Weighted Trees

作　　者：李建平[1] 刘旭[1] 朱娟萍[1] 

机构地区：[1]云南大学数学系,昆明650091

出　　处：《运筹学学报》2009年第2期111-118,共8页Operations Research Transactions

基　　金：国家自然科学基金(No.10861012;10561009);云南省自然科学基金(No.2006F0016M;2007A175M);云南省中青年学术技术带头人后备人才培养基金(No.2007PY01-21)资助项目

摘　　要：图G=(V,E;f,w)是顶点和边都赋权的树,f:V→R^+,w:E→R^+.本文给出了顶点u与v之间距离的一种新的定义.在顶点和边都赋权的树中,研究在新距离条件下的r-控制集问题与k-中心问题.对于r-控制集问题,设计出了复杂性为■(n)的多项式时间算法;对于k-中心问题,设计出了■(n^2 log n)的多项式时间算法.Let G = （V, E; f, w） be a weighted tree of order n, where f ： V→R^＋, w ： E → R^＋. In this paper, a new distance between u and v is defined. We study the r-dominating set problem and the k-center problem under this new distance in such weighted trees. For the new distance definition, we design an algorithm to solve the r- dominating set problem in weighted trees, which runs in time O（n）. And we also design an algorithm to solve the k-center problem in weighted trees, which runs in time O（n^2 log n）, where n is the order of the tree.

关 键 词：运筹学 网络 r-控制集 k-中心 多项式时间算法 

分 类 号：O175.1[理学—数学] O157.5[理学—基础数学]