# Accession Number:

## AD0699933

# Title:

## A NETWORK ISOLATION ALGORITHM,

# Descriptive Note:

# Corporate Author:

## MITRE CORP MCLEAN VA

# Personal Author(s):

# Report Date:

## 1969-12-01

# Pagination or Media Count:

## 29.0

# 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 ce. 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

# Descriptors:

# Subject Categories:

- Operations Research
- Command, Control and Communications Systems