摘要
图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.
出处
《运筹学学报》
CSCD
2009年第2期111-118,共8页
Operations Research Transactions
基金
国家自然科学基金(No.10861012
10561009)
云南省自然科学基金(No.2006F0016M
2007A175M)
云南省中青年学术技术带头人后备人才培养基金(No.2007PY01-21)资助项目
关键词
运筹学
网络
r-控制集
k-中心
多项式时间算法
Operations research, network, r-dominating set, k-center, polynomialtime algorithms
