论文部分内容阅读
图G=（V,E；f，w）是顶点和边都赋权的树，f：V→R^＋，w：E→R^＋．本文给出了顶点u与v之间距离的一种新的定义．在顶点和边都赋权的树中，研究在新距离条件下的r-控制集问题与k-中心问题．对于r-控制集问题，设计出了复杂性为O（n）的多项式时间算法；对于k-中心问题，设计出了O（n^2 log n）的多项式时间算法．