#### Title

The k-neighbor, r-domination problems on interval graphs

#### Keywords

Computers; Facilities; Graphs; Location; Networks

#### 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 ⊆ V such that, for every vertex u ε{lunate} 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; and 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(N, M)). © 1994.

#### Publication Date

12-8-1994

#### Publication Title

European Journal of Operational Research

#### Volume

79

#### Issue

2

#### Number of Pages

352-368

#### Document Type

Article

#### Identifier

scopus

#### Personal Identifier

scopus

#### DOI Link

https://doi.org/10.1016/0377-2217(94)90364-6

#### Copyright Status

Unknown

#### Socpus ID

43949158601 (Scopus)

#### Source API URL

https://api.elsevier.com/content/abstract/scopus_id/43949158601

#### STARS Citation

Joshi, Dipti S.; Radhakrishnan, Sridhar; and Chandrasekharan, N., "The k-neighbor, r-domination problems on interval graphs" (1994). *Scopus Export 1990s*. 6.

https://stars.library.ucf.edu/scopus1990/6