欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
图G=（V,E；f，w）是顶点和边都赋权的树，f：V→R^＋，w：E→R^＋．本文给出了顶点u与v之间距离的一种新的定义．在顶点和边都赋权的树中，研究在新距离条件下的r-控制集问题与k-中心问题．对于r-控制集问题，设计出了复杂性为O（n）的多项式时间算法；对于k-中心问题，设计出了O（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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：