Balancing collections of vertices in a network

Details Balancing collections of vertices in a network Balancing collections of vertices in a network

2007-03-06

2010-06-22

Rodriguez, Paul L (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Simulating electronic device or electrical system

Reexamination Certificate

active

07742906

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.

REFERENCES:
patent: 6999420 (2006-02-01), Chiu
patent: 2004/0267648 (2004-12-01), Schaub
patent: 2008/0109392 (2008-05-01), Nandy
Bar-ilan et al. 1993. http://eprints.kfupm.edu.sa/44230. “How to allocate network centers”. p. 1-30.
Zhang et al., U.S. Appl. No. 11/048,301, entitled “System and Method for Selecting a Portfolio,” filed Jan. 30, 2005, pp. 1-22, Figs. 1 -4.
Zhang et al., U.S. Appl. No. 11/159,454, entitled “Determination of a State of Flow Through or a Cut of a Parameterized Network,” filed Jun. 22, 2005, pp. 1-24, Fig. 1-6.
Zhang et al., U.S. Appl. No. 11/340,081, entitled “Determining an Amount of Flow Through, or a Cut of, a Parameterized Network,” pp. 1-23, Figs. 1-7, Jan. 25, 2006.
Tarjan et al., U.S. Appl. No. 11/450,706, entitled “Identifying a Minimum Cut and/or a Maximum Flow Using Balancing of Vertex Excesses,” filed Jun. 9, 2006, pp. 1-24, Figs. 1-5.
J.W.J. Williams, “Algorithm 232 Heapsort,” Communications of the ACM, vol. 7, No. 6, pp. 347-349 (Jun. 1964).
J. Misra et al., “A Constructive Proof of Vizing's Theorem,” Information Processing Letters 41(3), pp. 131-133 (Sep. 1990).
A. Goldberg et al., “Beyond the Flow Decomposition Barrier,” Journal of ACM, 45(5), pp. 783-797. (Sep. 1998).
B.V. Cherkassky et al., “On Implementing Push-Relabel Method for the Maximum Flow Problem,” Algorithmica 19(4), pp. 390-410 (Sep. 1994).
D.D. Sleator et al., “A Data Structure for Dynamic Trees,” Journal of Computer and System Sciences, vol. 26, No. 3, pp. 362-391 (Jun. 1983).
A. Goldberg et al., “Finding Minimum-Cost Circulations by Successive Approximation,” Mathematics of Operations Research, vol.15, No. 3, pp. 430-465 (Aug. 1990>.
A.V. Goldberg et al., “A New Approach to the Maximum-Flow Problem,” Journal of the Association for Computing Machinery, vol. 35, No. 4, pp. 921-940 (Oct. 1988).
D. Hochbaum, “The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem,” Proceedings of 6th International Conference on Integer Programming and Combinatorial Optimization, pp. 325-337 (Jun. 1998).
http:\\magma.maths.usyd.edu.au/magma/htmlhelp/text1417.htm, “Maximum Flow and Minimum Cut,” pp. 1-7 (at least as early as Nov. 17, 2005).
http:\\128.32.125.151/riot/Applications/WeightedMinCut/, “The Minimum/Maximum Cut Problem” pp. 1-3 (at least as early as Nov. 17, 2005).
http:\\mathworld.wolfram.com/MaximumFlowMinimumCutTheorem.html., “Maximum Flow, Minimum Cut Theorem,” p. 1 (at least as early as Nov. 27, 2005).
http:\\people.brunel.ac.uk/ mastjjb/jeb/or
etflow.html, “OR-Notes,” pp. 1-14 (at least as early as Nov. 17, 2005).
http:\\mathworld.wolfram.com/NetworkFlow.html, “Network Flow,” pp. 1-2 (at least as early as. Nov. 17, 2005).
B. Zhang et al., “A Simultaneous Parametric Maximum-Flow Algorithm for Finding the Complete Chain of Solutions,” pp. 1-15, Oct. 25, 2004.
B. Zhang et al., “Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing,” pp. 1-8, Jun. 28, 2005.
B. Zhang et al., “A Simultaneous Maximum Flow Algorithm for the Selection Model,” pp. 1-6, May 13, 2005.
Blum et al., Time Bounds for Selection, vol. 7, No. 4, Aug. 1973 (15 pages).
Tarjan et al., Balancing Applied to Maximum Network Flow Problems (Extended Abstract), Sep. 11-13, 2006 (12 pages).
U.S. Appl. No. 11/450,706, Non-Final Rejection dated Apr. 2, 2009, pp. 1-11 and attachments.
U.S. Appl. No. 11/450,706, Notice of Allowance dated Nov. 25, 2009, pp. 1-4 and attachments.

Affiliated with

Also associated with

Rating

Balancing collections of vertices 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 Balancing collections of vertices in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balancing collections of vertices in a network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4221150