#### Title

The K-Neighbor, R-Domination Problems On Interval-Graphs

#### Abbreviated Journal Title

Eur. J. Oper. Res.

#### Keywords

COMPUTERS; FACILITIES; LOCATION; GRAPHS; NETWORKS; Management; Operations Research & Management Science

#### Abstract

Many facility location problems are modeled as optimization problems on graphs. We consider the following facility location problem. Given a graph G = (V, E) with N vertices and M edges, the k-neighbor, r-dominating set ((k, r)-dominating set) problem is to determine the minimum cardinality set D subset-or-equal-to V such that, for every vertex u is-an-element-of V - D the distance between vertex u and at least k vertices in D is less than or equal to r. If we impose the condition that the graph induced by vertices in D should be connected, then the set D is a connected (k, r)-dominating set; if for each vertex in D there exists another vertex in D at a distance at most r, then the set D is a total(k, r)-dominating set; and if for each vertex in D there exists another vertex in D adjacent to it, then the set D is a reliable (k, r)-dominating set. In this paper, we present algorithms which run in O(k . N) time for solving the above problems on interval graphs, given its interval representation in sorted order. For the value of r = 1, our algorithms have a time-complexity of O(min(kN, M)).

#### Journal Title

European Journal of Operational Research

#### Volume

79

#### Issue/Number

2

#### Publication Date

1-1-1994

#### Document Type

Article

#### Language

English

#### First Page

352

#### Last Page

368

#### WOS Identifier

#### ISSN

0377-2217

#### Recommended Citation

"The K-Neighbor, R-Domination Problems On Interval-Graphs" (1994). *Faculty Bibliography 1990s*. 1077.

http://stars.library.ucf.edu/facultybib1990/1077

## Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu