A NETWORK ISOLATION ALGORITHM,

Abstract

A set of edges D (called an isolation set) is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge e of the network is a positive cost c(e). The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. The paper formulates the problem of determining the minimal cost isolation as a 0-1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual sub-problems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound. (Author)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1969
Accession Number
AD0699933

Entities

People

  • G. Bennington
  • M. Bellmore
  • S. Lubore

Organizations

  • MITRE Corporation

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Colorado
  • Computer Programming
  • Cooperation
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Simplex Method

Fields of Study

  • Computer science

Readers

  • Fault Tolerant Diagnosis of Black and White Balloon Isolation Tests Using ¥.
  • Graph Algorithms and Convex Optimization.
  • Operations Research