Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1093.90072
Horne, Jennifer A.; Smith, J.Cole
Dynamic programming algorithms for the conditional covering problem on path and extended star graphs. (English)
[J] Networks 46, No. 4, 177-185 (2005). ISSN 0028-3045; ISSN 1097-0037/e

Summary: The Conditional Covering Problem (CCP) is a facility location problem on a graph, where the set of nodes represents demand points and potential facility locations. The key aspect of the CCP is that each facility covers all nodes within a given facility-specific coverage radius, except for the node at which it is located. The objective of this problem is to minimize the sum of the facility location costs required to cover all demand points. We first discuss the worst-case complexity of the CCP by examining literature related to the total domination problem, which is a special case of the CCP. Next, we examine the special case of path graphs and provide an $O(n^2)$ algorithm for its solution. Finally, we leverage information obtained from this procedure to derive an optimal algorithm for ``extended star'' graphs (multiple paths having one node in common), without increasing the worst-case complexity of the algorithm.

MSC 2000:: *90C39 Dynamic programming
90B80 Discrete location and assignment
05C69 Dominating sets, independent sets, cliques
05C70 Factorization, etc.
90B10 Flows in networks
90C35 Network programming

Keywords: conditional covering problem; facility location; dynamic programming; total domination

Cited in: Zbl 1205.05229

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]