A Dynamic programming algorithm for the Conditional Covering Problem on tree graphs

Jennifer A. Horne, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In a previous article, we presented algorithms for solving the Conditional Covering Problem (CCP) on path and extended star graphs. The CCP on these graphs can be solved in O(n 2) time, where n is the number of nodes in the graph. In this article, we propose a new dynamic programming procedure to solve the CCP on tree graphs. This recursion works from the leaf nodes of the tree up to the root node, using notions of protected and unprotected costs as done for the CCP path algorithm in our previous work. We introduce new preliminary routines and data structures to merge information from subpaths and subtrees, resulting in an O(n 4) algorithm to optimally solve the problem.

Original languageEnglish (US)
Pages (from-to)186-197
Number of pages12
JournalNetworks
Volume46
Issue number4
DOIs
StatePublished - Dec 1 2005
Externally publishedYes

Keywords

  • Conditional covering problem
  • Facility location; dynamic programming
  • Total domination
  • Tree graphs

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'A Dynamic programming algorithm for the Conditional Covering Problem on tree graphs'. Together they form a unique fingerprint.

Cite this