图的增广支配数 |
| |
引用本文: | 蔡延光.图的增广支配数[J].湖北汽车工业学院学报,1999,13(1):73-80. |
| |
作者姓名: | 蔡延光 |
| |
摘 要: | 增广p一中心是在原有的服务设施基础上增加p个设施为网络中的顶点提供紧急服务,因此增广p一中心问题比经典的p一中心问题更具有实际意义。本文提出了图的增广支配集、增广支配数的概念,这些概念与增广p一中心问题密切相关,给出了求任意图全部极小增广支配集的布尔方法,提出了一个线性时间的算法求树的增广支配数。
|
关 键 词: | 网络选址 支配数 布尔方法 增广支配数 线性时间算法 树 |
Augmented Domination Number of a Graph |
| |
Abstract: | 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.' |
| |
Keywords: | Network location domination number Boolean method augmented domination number linear time algorithm tree |
本文献已被 维普 等数据库收录! |