Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5184| Title: | Some Recent Advances in Network Flows |
| Issue Date: | 9-Oct-2013 |
| Publisher: | Massachusetts Institute of Technology, Operations Research Center |
| Description: | The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity on the algorithmic aspects of network flow problems over the past few years has been particularly striking. Several techniques have proven to be very successful in permitting researchers to make these recent contributions: (i) scaling of the problem data; (ii) improved analysis of algorithms, especially amortized average case performance and the use of potential functions; and (iii) enhanced data structures. In this survey, we illustrate some of these techniques and their usefulness in developing faster network flow algorithms. Our discussion focuses on the design of faster algorithms from the worst case perspective and we limit our discussion to the following fundamental problems: the shortest path problem, the maximum flow problem, and the minimum cost flow problem. We consider several representative algorithms from each problem class including the radix heap algorithm for the shortest path problem, preflow push algorithms for the maximum flow problem, and the pseudoflow push algorithms for the minimum cost flow problem. |
| URI: | http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
| Other Identifiers: | http://hdl.handle.net/1721.1/5184 |
| Appears in Collections: | MIT Items |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.