Method of identifying all minimum-cost cutsets in a network
US6594624B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 1, 1999 |
| Grant date | Jul 15, 2003 |
| Priority date | — |
| Expiry date | Sep 1, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/18
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention is a method of identifying all minimum-cost cutsets in a network to isolate two nodes S and T, by receiving a network that includes nodes and links; replacing each bidirectional link with two unidirectional links; assigning a cost to each node and link; choosing nodes S and T; removing any extraneous nodes and links that are not along a path from S to T; adding a node next to each original node; moving the links directed out of the original node to its added node; adding a link directed out of the original node and into its added node; assigning a cost to each added link that is equal to the cost of the corresponding original node; finding the paths from S to T that maximize the amount of flow from S to T, where flow capacity is equal to cost; generating a residual graph; finding each set of nodes in the residual graph that includes S, does not include T, and does not include a link directed from a node within the set to a node outside of the set; finding, for each closure, any links connected to the closure that are not members of the closure; choosing the minimum-cost cutset on which is most convenient to act; and eliminating the links and nodes as required …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.