Algorithms for solving the conditional covering problem on paths

Brian J. Lunday, J. Cole Smith and Jeffrey B. Goldberg

Naval Research Logistics (NRL), 2005, vol. 52, issue 4, 293-301

Abstract: Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear‐time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial‐time, dynamic programming algorithm to find the optimal solution. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.

Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20074

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:52:y:2005:i:4:p:293-301

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().