Efficient preflow push algorithms |
| |
Authors: | R. Cerulli M. Gentili A. Iossa |
| |
Affiliation: | 1. Dipartimento di Matematica ed Informatica, Università di Salerno, Via Ponte Don Melillo, 84084 Fisciano (SA), Italy;2. Dipartimento di Statistica, Probabilità e Statistiche Applicate, Università degli Studi di Roma “La Sapienza”, Piazzale A. Moro 5, 00185 Roma, Italy |
| |
Abstract: | Algorithms for the maximum flow problem can be grouped into two categories: augmenting path algorithms [Ford LR, Fulkerson DR. Flows in networks. Princeton University Press: Princeton, NJ: 1962], and preflow push algorithms [Goldberg AV, Tarjan RE. A new approach to the maximum flow problem. In: Proceedings of the 18th annual ACM symposium on theory of computing, 1986; p. 136–46]. Preflow push algorithms are characterized by a drawback known as ping pong effect. In this paper we present a technique that allows to avoid such an effect and can be considered as an approach combining the augmenting path and preflow push methods. An extended experimentation shows the effectiveness of the proposed approach. |
| |
Keywords: | Maximum flow Ping pong effect Preflow push |
本文献已被 ScienceDirect 等数据库收录! |
|