The distance-domination numbers of trees |
| |
Authors: | Wen-Lian Hsu |
| |
Affiliation: | The Technological Institute, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60201, U.S.A. |
| |
Abstract: | The P-center problem is to locate P centers in a graph G so that the maximum distance between centers and non-centers is minimized. A related problem is to determine the maximum number of vertices that can be “covered” (within a distance of α) by a vertex set of cardinality P in G. In this paper we describe an O(n3P) algorithm which solves the maximum coverage problem on trees. We also apply the same idea to solve the P-median problem on trees. |
| |
Keywords: | Dominating set chordal graphs |
本文献已被 ScienceDirect 等数据库收录! |