Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1205.05229
Sivan, Balasubramanian; Harini, S.; Rangan, C.Pandu
On conditional covering problem.
(English)
[J] Math. Comput. Sci. 3, No. 1, 97-107 (2010). ISSN 1661-8270; ISSN 1661-8289/e

Summary: The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by {\it J. A. Horne} and {\it J. C. Smith} [Networks 46, No. 4, 177--185 (2005; Zbl 1093.90072)]. We show that their algorithm is wrong and further present a correct $O(n ^{3})$ algorithm for the same. We also propose an $O(n ^{2})$ algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.
MSC 2000:
*05C85 Graphic algorithms
05C69 Dominating sets, independent sets, cliques
05C70 Factorization, etc.
90C39 Dynamic programming
90B80 Discrete location and assignment

Keywords: conditional covering problem; facility location; total domination problem; paths; interval graphs

Citations: Zbl 1093.90072

Highlights
Master Server