#### Title

A Fast Algorithm For Generalized Network Location Problems

#### Keywords

Computers; Facilities; Graphs; Location; Networks

#### Abstract

Location models on networks typically have a set of clients who have demand for services or commodities, and facilities to serve the clients. Location problems have many applications in the area of operations research. Various problems arise while imposing constraints on the clients and/or the facilities. One of the constraints could be to use a minimum number of resources and yet satisfy the clients' need. One of the classical location problem is the domination problem. Domination problems on graphs are the optimization versions of the facility location problems on networks. The domination problem seeks to determine a minimum number of vertices D (client regions) such that every other vertex is adjacent to at least one member in D. The set D of vertices are the client locations where the facilities would be placed. In this paper, we consider a general domination problem on graphs which is defined below. The (k,r)-domination problem is the problem of selecting a minimum cardinality vertex set D of a graph G = (V, E) such that every vertex x not in D is at a distance r or less from at least ib vertices in D. This gives the solution to the location problems where the clients need at least k facilities within a distance of r. If we impose the condition that for each vertex in D there exist another vertex in D at a distance of at most r, then the set D is a total (k,r)-dominating set, and if for each vertex in D there exist 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 0(k•N) time for solving the generalized location problems on interval graphs, given its interval representation in sorted order.

#### Publication Date

3-1-1993

#### Publication Title

Proceedings of the ACM Symposium on Applied Computing

#### Volume

Part F129680

#### Number of Pages

701-708

#### Document Type

Article; Proceedings Paper

#### Identifier

scopus

#### Personal Identifier

scopus

#### DOI Link

https://doi.org/10.1145/162754.167181

#### Copyright Status

Unknown

#### Socpus ID

33750356040 (Scopus)

#### Source API URL

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

#### STARS Citation

Joshi, Dipti S.; Radhakrishnan, Sridhar; and Narayanan, Chandrasekheran, "A Fast Algorithm For Generalized Network Location Problems" (1993). *Scopus Export 1990s*. 559.

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