Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1093.90073
Horne, Jennifer A.; Smith, J.Cole
A dynamic programming algorithm for the conditional covering problem on tree graphs. (English)
[J] Networks 46, No. 4, 186-197 (2005). ISSN 0028-3045; ISSN 1097-0037/e

Summary: In a previous article [ibid. 46, No. 4, 177--185 (2005; Zbl 1093.90068)], we presented algorithms for solving the Conditional Covering Problem (CCP) on path and extended star graphs. The CCP on these graphs can be solved in $O(n^2)$ time, where $n$ is the number of nodes in the graph. In this article, we propose a new dynamic programming procedure to solve the CCP on tree graphs. This recursion works from the leaf nodes of the tree up to the root node, using notions of protected and unprotected costs as done for the CCP path algorithm in our previous work. We introduce new preliminary routines and data structures to merge information from subpaths and subtrees, resulting in an $O(n^4)$ algorithm to optimally solve the problem.

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; tree graphs; total domination

Citations: Zbl 1093.90068

Cited in: Zbl 1235.05110

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]