Name
Abstract | ||
|---|---|---|
In a previous article, 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(n2) 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(n4) algorithm to optimally solve the problem. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 186–197 2005 |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1002/net.v46:4 | Networks |
Keywords | Field | DocType |
dynamic programming,dynamic programming algorithm,facility location,tree graphs | Discrete mathematics,Data structure,Dynamic programming,Combinatorics,Mathematical optimization,Tree (graph theory),Chordal graph,Facility location problem,Star (graph theory),Longest path problem,Recursion,Mathematics | Journal |
Volume | Issue | ISSN |
46 | 4 | 0028-3045 |
Citations | PageRank | References |
3 | 0.49 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jennifer A. Horne | 1 | 7 | 1.00 |
| J. Cole Smith | 2 | 610 | 43.34 |