Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]