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

Socpus ID

33750356040 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS