A dynamic programming algorithm for the generalized minimum filter placement problem on tree structures

E. Chisonge Mofya, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a network where nodes communicate by exchanging information packets whose fields include the address of the sending node and that of the destination node. In the absence of some verification mechanism, an attacking node can send packets to another node using a forged origin address. In this study, we consider an optimization problem of identifying a minimum cardinality subset of verification nodes on a tree such that the number of attacks from any forged origin to any destination is limited to a prescribed level. For the case in which communication is permitted between every node in the tree, we develop an optimal polynomial-time dynamic programming algorithm for this problem. We compare the performance of the dynamic programming algorithm against a mixed-integer programming model on randomly generated tree networks at varied levels of security.

Original languageEnglish (US)
Pages (from-to)322-332
Number of pages11
JournalINFORMS Journal on Computing
Volume21
Issue number2
DOIs
StatePublished - Mar 1 2009
Externally publishedYes

Keywords

  • Dynamic programming
  • Network communication
  • Route-based filter

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A dynamic programming algorithm for the generalized minimum filter placement problem on tree structures'. Together they form a unique fingerprint.

Cite this