摘要
增广ｐ一中心是在原有的服务设施基础上增加ｐ个设施为网络中的顶点提供紧急服务，因此增广ｐ一中心问题比经典的ｐ一中心问题更具有实际意义。本文提出了图的增广支配集、增广支配数的概念，这些概念与增广ｐ一中心问题密切相关，给出了求任意图全部极小增广支配集的布尔方法，提出了一个线性时间的算法求树的增广支配数。
Augmented p-center is a class of problems that decides the positions of p new facilities that serve the all venices in a network along with the original facilities. It is obvious that the concept of augmented p-center is more meaningful than that of p -center. This paper presents the concepts of augmented dominating set and augmented domination number of a graph,which are closely related to the augment p-center. A Boolean method is given to find all minimal augmented dominationg sets of a graph. A linear time algorithmeis designed to determine the minimum augmented dominationg set of a tree. Computing examples are also given to demonstrate these algorithms.'
出处
《湖北汽车工业学院学报》
1999年第1期73-80,共8页
Journal of Hubei University Of Automotive Technology
关键词
网络选址
支配数
布尔方法
增广支配数
线性时间算法
树
Network location
domination number
Boolean method
augmented domination number
linear time algorithm
tree
