### 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(n ^{2}) 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.

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

Pages (from-to) | 177-185 |

Number of pages | 9 |

Journal | Networks |

Volume | 46 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 2005 |

Externally published | Yes |

### Keywords

- Conditional covering problem
- Dynamic programming
- Facility location
- Total domination

### ASJC Scopus subject areas

- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications

## Fingerprint Dive into the research topics of 'Dynamic programming algorithms for the Conditional Covering Problem on path and extended star graphs'. Together they form a unique fingerprint.

## Cite this

*Networks*,

*46*(4), 177-185. https://doi.org/10.1002/net.20086