Paper Info
Title
Dynamic programming algorithms for the conditional covering problem on path and extended star graphs
Abstract
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(n2) 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. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 177–185 2005
Year
DOI
Venue
2005
10.1002/net.v46:4
Networks
Keywords
Field
DocType
star graph,dynamic programming algorithm,facility location,dynamic programming
Multipath propagation,Graph,Dynamic programming,Mathematical optimization,Dominating set,Combinatorics,Algorithm,Star (graph theory),Facility location problem,1-center problem,Mathematics,Special case
Journal
Volume
Issue
ISSN
46
4
0028-3045
Citations 
PageRank 
References 
4
0.50
5
Authors
2
Name
Order
Citations
PageRank
Jennifer A. Horne171.00
J. Cole Smith261043.34