R -Domination in Graphs

1 July 1976

journal article
Published by Association for Computing Machinery (ACM) in Journal of the ACM

Vol. 23 (3) , 446-450
https://doi.org/10.1145/321958.321964

Abstract

The problem of finding a minimum k -basis of graph G is that of selecting as small a set B of vertices as possible such that every vertex of G is at distance k or less from some vertex in B . Cockayne, Goodman, and Hedetniemi previously developed a linear algorithm to find a minimum 1-basis (a minimum dominating set) when G is a tree. In this paper the k -basis problem is placed in a more general setting, and a linear algorithm is presented that solves the problem for any forest.

Keywords

MINIMUM K-BASIS
MINIMUM 1-BASIS
B. COCKAYNE
MINIMUM DOMINATING SET
GENERAL SETTING
GRAPH G
DISTANCE K
SET B
LINEAR ALGORITHM
K-BASIS PROBLEM

This publication has 0 references indexed in Scilit: