Balancing collections of vertices in a network

1. A method executable in a computer, comprising:

providing a representation of a network having vertices connected by arcs; and

iteratively selecting, by the computer, different collections of vertices in the network in which to perform moves for balancing the corresponding collections of the network, wherein the collections are represented by corresponding graphs according to a predefined structure,

wherein balancing each of the collections of vertices comprises computing a balanced pseudoflow for vertices arranged in a star, the star having a center vertex and adjacent vertices around the center vertex, and wherein computing the balanced pseudoflow comprises:

identifying minimum and maximum excesses for each of the adjacent vertices, wherein the minimum and maximum excesses form a set;

selecting an interval from among plural intervals defined by the minimum and maximum excesses;

computing an excess for the center vertex; and

determining whether the excess for the center vertex is in the selected interval.

2. The method of claim 1 , further comprising indicating that the computed excess is a final excess for the center vertex in response to determining that the computed excess is in the selected interval.

3. The method of claim 1 , further comprising:

in response to determining that the computed excess is not in the selected interval,

(a) discarding some of the minimum and maximum excesses from the set to form an updated set,

(b) selecting an interval I m from the updated set,

(c) recomputing an excess for the center vertex;

(d) determining whether the recomputed excess for the center vertex is in the interval I m ,

(e) repeating steps (a)-(d) by iterating through m until it is determined that the recomputed excess for the center vertex is in the interval I m , and

using the recomputed excess that is in the interval I m , as the final excess of the center vertex.

4. The method of claim 1 , wherein selecting the interval comprises selecting the interval by one of

(1) finding a median value in the set and identifying the interval based on the median value, and

(2) selecting a random value and identifying the interval based on the selected random value.

5. The method of claim 1 , further comprising:

determining the final excess for the center vertex; and

computing flows over edges between the adjacent vertices and the center vertex based on the final excess for the center vertex.

6. The method of claim 5 , further comprising:

identifying plural subsets of the adjacent vertices;

for a first of the plural subsets, seeking a final excess of each of the adjacent vertices in the first subset equal to a corresponding maximum excess, wherein each of the maximum excesses corresponding to the adjacent vertices in the first subset is less than the final excess of the center vertex;

for a second of the plural subsets, setting a final excess with each of the adjacent vertices in the second subset equal to a corresponding minimum excess, wherein each of the minimum excesses corresponding to the adjacent vertices in the second subset is greater than the final excess of the center vertex; and

for a third of the plural subsets, setting a final excess of each of the adjacent vertices in the third subset equal to the final excess of the center vertex.

7. The method of claim 1 , wherein balancing the collections comprises balancing vertices of a parametric bipartite network.

8. The method of claim 1 , wherein providing the representation of a network comprises providing a representation of one of a computer network system, a computer, a transportation system, a hydraulic system, a communications system, a financial system, a scheduling system, a location and layout determination system, a warehouse and distribution system, a production planning and control system, and an energy reduction system.

9. A method executable in a computer, comprising:

providing a representation of a network having vertices connected by arcs;

iteratively selecting, by the computer, different collections of vertices in the network in which to perform moves for balancing the corresponding collections of the network, wherein the collections are represented by corresponding graphs according to a predefined structure;

identifying the collections of vertices as paths in the network, wherein each of the paths includes a succession of vertices, wherein each of the paths is a monotone path in which excesses associated with the vertices in the corresponding monotone path are non-increasing or non-decreasing along the corresponding monotone path, wherein at least a particular one of the monotone paths is dividable into plural groups; and

iteratively combining groups of the particular monotone path to balance the vertices of the particular monotone path.

10. The method of claim 9 ,

wherein combining the groups comprises combining at least two of the groups to form a combination group; and the method further comprising:

computing a common excess for the vertices of the combination group, wherein the common excess is a weighted average of the excesses of the vertices in the at least two groups.

11. A method executable in a computer, comprising:

providing a representation of a network having vertices connected by arcs;

iteratively selecting, by the computer, different collections of vertices in the network in which to perform moves for balancing the corresponding collections of the network, wherein the collections are represented by corresponding graphs according to a predefined structure;

identifying the collections of vertices as paths in the network, wherein each of the paths includes a succession of vertices;

for each vertex of a particular one of the paths, computing a first excess and a second excess;

combining the vertices of the particular path into first groups of vertices, wherein in each first group the vertices have a common first excess; and

combining the vertices of the particular path into second groups of vertices, wherein in each second group the vertices have a common second excess;

defining a frozen part of the particular path in which vertices are balanced;

comparing one of the common first excesses with one of the common second excesses; and

moving vertices associated with the second group associated with the one common second excess into the frozen part based on the comparing.

12. A computer-usable storage medium storing instructions that when executed cause a computer to:

represent a network with a graph having vertices connected by arcs; and

iteratively select different trees of vertices in the graph in which to perform moves for balancing the corresponding trees of the network, wherein each tree has a root vertex and leaf vertices, and wherein balancing a particular one of the trees comprises:

computing a function for each of the leaf vertices in the particular tree, wherein a value of the function varies with an excess value of each corresponding leaf vertex;

computing functions for corresponding non-leaf vertices of the particular tree using a bottom-up procedure, wherein the functions for the corresponding non-leaf vertices that are parents of the leaf vertices are based on the functions for the leaf vertices; and

computing flow values in the particular tree using the functions computed for the leaf vertices and non-leaf vertices.

13. The article of claim 12 , wherein computing the functions using the bottom-up procedure comprises computing the functions for non-leaf vertices using one of sorted lists and binary search trees to represent values associated with child vertices.