Dynamic programming algorithms for the Conditional Covering Problem on path and extended star graphs

Jennifer A. Horne, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

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 languageEnglish (US)
Pages (from-to)177-185
Number of pages9
JournalNetworks
Volume46
Issue number4
DOIs
StatePublished - Dec 2005
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Information Systems
  • 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