
Accession Number : AD0699933
Title : A NETWORK ISOLATION ALGORITHM,
Corporate Author : MITRE CORP MCLEAN VA
Personal Author(s) : Bennington,G. ; Lubore,S. ; Bellmore,M.
Report Date : DEC 1969
Pagination or Media Count : 29
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 01 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems 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 : (*COMMUNICATION SYSTEMS, VULNERABILITY), (*GRAPHICS, NETWORKS), COMMAND AND CONTROL SYSTEMS, LINEAR PROGRAMMING, ALGORITHMS
Subject Categories : Operations Research
Command, Control and Communications Systems
Distribution Statement : APPROVED FOR PUBLIC RELEASE