A Fast Algorithm For Generalized Network Location Problems


Computers; Facilities; Graphs; Location; Networks


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


Publication Title

Proceedings of the ACM Symposium on Applied Computing


Part F129680

Number of Pages


Document Type

Article; Proceedings Paper



Personal Identifier


DOI Link


Socpus ID

33750356040 (Scopus)

Source API URL


This document is currently not available here.