Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-09-01
2003-07-15
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C709S238000, C709S240000, C709S241000, C370S351000
Reexamination Certificate
active
06594624
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates, in general, to information processing system organization and, in particular, to flow controlling.
BACKGROUND OF THE INVENTION
Any network of items may be represented as a graph using nodes and links, where each node represents an item in the network, and where each link represents a connection from one node to another. Examples of such networks include telephone networks, integrated circuits, computer networks, infrastructure networks (e.g., roads, trains, etc.), and so on.
The ability to analyze the links and nodes in a graph according to certain criteria is useful for many different purposes. For example, a electric company may wish to isolate, or remove, a substation from its power grid due to a malfunction at that substation. A designer may wish to determine the optimum placement of circuit components on an integrated circuit to optimize circuit performance. Operators of a computer network (e.g., the INTERNET) may wish to isolate a computer from the network if the computer become infected with a virus and thus prevent other computers in the network from becoming infected with the virus. A set of links or nodes to be removed from a graph to isolate one node from another node is often referred to as a cutset.
In an article entitled “Vertex Cutsets of Undirected Graphs,” published June 1995, in IEEE
Transactions on Reliability
, Vol. 44, No. 2, C. Patvardhan et al. disclosed a method of identifying every possible cutset for isolating two nodes from one another, regardless of the cost associated with cutting a node or link. Since the number of possible cutsets for isolating two nodes from one another grows exponentially as the number of nodes and/or links increases, the method disclosed by Patvardhan et al. becomes computationally prohibitive when dealing with a large network. The present invention discloses a computationally efficient method of finding links and, possibly, nodes, that cost the least to cut, or eliminate, to isolate two user-selected nodes from each other.
In an article entitled “Experimental Study of Minimum Cut Algorithms,” published 1997, in
Proceedings of the
8
th Annual
ACM-SIAM
Symposium on Discrete Algorithms
, Chandra S. Chekuri et al. disclosed a survey of the most efficient cutset algorithms available in 1997. The algorithms disclosed therein find one cutset that minimizes the cost associated with cutting the links, but do not find all of the possible cutsets that minimize the cost associated with cutting the links as does the present invention.
U.S. Pat. No. 5,666,290, entitled “INTERACTIVE TIME-DRIVEN METHOD OF COMPONENT PLACEMENT THAT MORE DIRECTLY CONSTRAINS CRITICAL PATHS USING NET-BASED CONSTRAINTS,” discloses a method of placing circuit components on an integrated circuit to optimize circuit performance by finding one cutset that minimizes cost. U.S. Pat. No. 5,666,290 does not disclose a method of finding all cutsets that minimize cost as does the present invention. U.S. Pat. No.5,666,290 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,748,844, entitled “GRAPH PARTITIONING SYSTEM,” discloses a device for partitioning a graph by starting with 100 cutsets, reducing the 100 to the best 20 and picking the best cutset therefrom. U.S. Pat. No. 5,748,844 does not disclose a method of finding all minimum cost cutsets as does the present invention. U.S. Pat. No. 5,748,844 is hereby incorporated by reference into the specification of the present invention.
SUMMARY OF THE INVENTION
It is an object of the present invention to identify, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node.
It is an object of the present invention to identify, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node, where the network is any suitable network such as a computer network, a telephone network, an infrastructure network, an integrated-circuit interconnection network, and so on.
The present invention is the first method of identifying, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node. The present invention is applicable to any suitable network such as a computer network, a telephone network, an infrastructure network, an integrated circuit interconnection network, and so on.
The first step of the present invention is receiving a suitable network, where the network includes nodes and links between the nodes. The links may be unidirectional or bidirectional.
The second step is replacing each bidirectional link with two unidirectional links, where the two unidirectional links are parallel to each other and directed in opposite directions from each other.
The third step is assigning a non-negative value, or cost, to each node and link in the network. The cost assigned to each node or link is the cost of eliminating, or cutting, that node or link from the network.
The fourth step is choosing two nodes in the network, a source node S and a termination node T, between which it is desired to find all minimum-cost cutsets.
The fifth step is removing any extraneous nodes and links that are not along a path from node S to node T.
The sixth step is adding a node next to each node that is original to the network.
The seventh step is moving, for each node that is original to the network, the links directed away from the node to its added node so that such links are directed away from the added node.
The eighth step is adding, to each node that is original to the network, a link directed out of the node and directed into its added node.
The ninth step is assigning a non-negative value, or cost, to each link added in the last step that is equal to the non-negative value, or cost, of the corresponding node that is original to the network.
The tenth step is finding the paths from node S to node T in the network as modified by steps two through nine that maximize flow from node S to node T. The flow capacity of a node, or link, is equal to the cost assigned to that node, or link.
The eleventh step is creating a residual graph of the network as modified by steps two through nine by including all original nodes of the network; including all nodes added to the network; including all links, with direction maintained, from the network that were not identified in the previous step as being a part of a maximum-flow path; including all links, with directions reversed, from the network that were identified as being a part of a maximum-flow path and carried flow at capacity; including all links, with direction maintained, from the network that were identified as being a part of a maximum-flow path and carried flow at less than capacity; and adding a link, in the opposite direction, for each link from the network that was identified as being a part of a maximum-flow path and carried flow at less than capacity. The residual graph contains non-maximum-cost paths from node S to node T from which will be found all minimum-cost cutsets for the network.
The twelfth step is finding each set of nodes in the residual graph that includes node S, does not include node T, and does not include a link directed from a node within the set to a node outside of the set. A set of nodes that meets the three criteria listed above is commonly referred to as a closure. All minimum-cost cutsets of the network are found using the closures of the residual graph. The number of minimum-cost cutsets of the network is less than or equal to the number of closures of the residual graph.
The thirteenth step is finding in the network as modified by steps two through nine, for each closure, any link directed from a node within the closure to a node outside of the closure. Such a set of links found for one particular closure constitutes one possible minimum-cost cutset for the network. The sets of links found for all of the closures constitute all of the possible minimum-cost cutsets for
Broda Samuel
Morelli Robert D.
Phan Thai
The United States of America as represented by the National Secu
LandOfFree
Method of identifying all minimum-cost cutsets in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of identifying all minimum-cost cutsets in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of identifying all minimum-cost cutsets in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3041596