Bounded Error Approximation Algorithms for Risk-Based Intrusion Response

Abstract

Our research consisted of modeling the intrusion response problem as one of finding a partial vertex cover in bipartite graphs. Prior to our work, intrusion response had not been studied within a graph-theoretic framework. Some of our important contributions include: (a) The partial vertex cover problem for matchings (PVCM) is poly time solvable, if either the vertices or the edges are weighted, but NP-hard, if both are weighted. (b) We show that the PVCM admits a fully polynomial approximation scheme, when both vertices and edges are weighted

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 17, 2015
Accession Number
ADA623073

Entities

People

  • K. Subramani

Organizations

  • West Virginia University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Availability
  • Classification
  • Computational Complexity
  • Computer Science
  • Computers
  • Contracts
  • Department Of Defense
  • Electronic Mail
  • Intrusion
  • Linear Programming
  • Polynomials
  • Scientific Research
  • West Virginia

Readers

  • Graph Algorithms and Convex Optimization.
  • Sensor Fusion and Tracking Systems.