Back to results
US 7,680,641 B1Granted
Identifying a minimum cut and/or a maximum flow using balancing of vertex excesses
AssigneeHewlett-Packard Development Company, L.P.
InventorsRobert E. Tarjan, Bin Zhang, Yunhong Zhou
Life of this patent
Estimating the term…
Abstract
A representation of a network having vertices connected by arcs is provided, where the network exhibits a pseudoflow. Arcs on which moves are to be performed are iteratively chosen for balancing excesses of vertices across the arcs until a stopping rule is satisfied. After the stopping rule is satisfied, further processing is performed to identify at least one of a minimum cut and/or maximum flow.
Claims19
A method comprising:
- providing a representation of a network having vertices connected by arcs, wherein the network exhibits a pseudoflow;
- iteratively choosing, by a computer, arcs of the network on which to perform moves for balancing excesses of vertices until a stopping rule is satisfied;
- after the stopping rule is satisfied, performing, by the computer, further processing to identify at least one of a minimum cut and maximum flow;
- and
- identifying an active section in the network, wherein iteratively choosing the arcs is performed in the active section but not in a portion of the network outside the active section.
2 more elements
A method comprising:
- providing a representation of a network having vertices connected by arcs, wherein the network exhibits a pseudoflow;
- iteratively choosing, by a computer, arcs of the network on which to perform moves for balancing excesses of vertices until a stopping rule is satisfied;
- and
- after the stopping rule is satisfied, performing, by the computer, further processing to identify at least one of a minimum cut and maximum flow;
- wherein performing the further processing to identify the minimum cut comprises:
- initially defining X and Y, where X contains a set of vertices including a source vertex of the network, and Y contains a set of all vertices in the network not including X, wherein Y contains a sink vertex of the network;
- and
- successively moving vertices from X to Y to modify the cut until no unsaturated arcs cross the modified cut,
- wherein the number of unsaturated arcs crossing cut (X, Y) is zero.
6 more elements
Instructions on a computer-usable medium that when executed cause a computer to:
- provide a representation of a network having vertices connected by arcs, wherein the network exhibits a pseudoflow;
- and
- perform a balancing loop to iteratively choose arcs of the network on which to perform moves across the arcs until a stopping rule is satisfied;
- after the stopping rule is satisfied, perform further processing to identify at least one of a minimum cut and maximum flow;
- and
- identifying an active section in the network, wherein performing the balancing loop is performed in the active section such that arcs are not chosen from a portion of the network outside the active section in performing the balancing loop.
3 more elements
A method comprising:
- providing a representation of a network having vertices connected by arcs, wherein the network exhibits a pseudoflow;
- iteratively choosing, by a computer, arcs of the network on which to perform moves across the arcs in an active section of the network to enable determination of at least one of a minimum cut and a maximum flow, wherein arcs in a portion of the network outside the active section are not chosen to perform moves;
- and
- iteratively reducing, by the computer, the size of the active section as the moves are made.
1 more element
Dependencies are inferred from the claim text.