Back to results
US 7,742,906 B2Granted
Balancing collections of vertices in a network
AssigneeHewlett-Packard Development Company, L.P.
InventorsYunhong Zhou, Robert E. Tarjan, Bin Zhang
Life of this patent
Estimating the term…
Abstract
A representation of a network having vertices connected by arcs is provided. Different collections of vertices in the network are iteratively selected. Balancing moves are performed in corresponding collections of the network, where the collections are represented by corresponding graphs according to a predefined structure.
Claims13
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.
6 more elements
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.
2 more elements
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.
8 more elements
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.
4 more elements
Dependencies are inferred from the claim text.