A network isolation algorithm

M. Bellmore, G. Bennington and S. Luhore

Naval Research Logistics Quarterly, 1970, vol. 17, issue 4, 461-469

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 of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This 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 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.

Date: 1970
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800170405

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:17:y:1970:i:4:p:461-469

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().