| Data: |
1997 |
| Resum: |
Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on an n-node, m-arc network in at most 2nm pivots and O(n^2m) time are presented. These rules are based on the concept of a preflow and depend upon the use of node labels which are either the lengths of a shortest pseudoaugmenting path from those nodes to the sink node or valid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. . |
| Drets: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.  |
| Llengua: |
Anglès |
| Document: |
Article ; recerca ; Versió publicada |
| Matèria: |
Dual simplex method ;
Maximum flow ;
Parametric maximum flow ;
Preflow ;
Pseudoaugmenting path ;
Strongly polynomial ;
Valid distance labels |
| Publicat a: |
Mathematical Programming, vol. 78 n. 2 (1997) p. 159-168, ISSN 0025-5610 |
visitant ::
identificació
Accés restringit a la UAB
