### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 293-301 |

Number of pages | 9 |

Journal | Naval Research Logistics |

Volume | 52 |

Issue number | 4 |

DOIs | |

State | Published - Jun 1 2005 |

Externally published | Yes |

### Keywords

- Covering problems
- Dynamic programming
- Location theory

### ASJC Scopus subject areas

- Modeling and Simulation
- Ocean Engineering
- Management Science and Operations Research

## Fingerprint Dive into the research topics of 'Algorithms for solving the conditional covering problem on paths'. Together they form a unique fingerprint.

## Cite this

*Naval Research Logistics*,

*52*(4), 293-301. https://doi.org/10.1002/nav.20074