Partitioning Algorithm for the Parametric Maximum Flow

Mircea Parpalea, Eleonor Ciurea

Department of Theoretical Computer Science, Transilvania University of Bra?ov, Bra?ov, Romania.
National College Andrei ?aguna, Bra?ov, Romania.

DOI: 10.4236/am.2013.410A1002                

Abstract

The article presents an approach to the maximum flow problem in parametric networks with linear capacity functions of a single parameter, based on the concept of shortest conditional augmenting directed path. In order to avoid working with piecewise linear functions, our approach uses a series of parametric residual networks defined for successive subintervals of the parameter values where the parametric residual capacities of all arcs remain linear functions. Besides working with linear instead piecewise linear functions, another main advantage of our approach is that every directed path in such a parametric residual network is also a conditional augmenting directed path for the subinterval for which the parametric residual network was defined. The complexity of the partitioning algorithm is O (Kn²m) where K is the number of partitioning points of the parameter values interval, n and m being the number of nodes, respectively the number of arcs in the network.

Keywords

Network Flow; Parametric Flow; Conditional Augmenting Paths

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Ahuja, T. Magnanti and J. Orlin, “Network Flows. Theory, Algorithms and Applications,” Prentice Hall Inc., Englewood Cliffs, 1993.
[2]	H. W. Hamacher and L. R. Foulds, “Algorithms for Flows with Parametric Capacities,” ZOR—Methods and Models of Operations Research, Vol. 33, No. 1, 1989, pp. 21-37.
[3]	G. Ruhe, “Complexity Results for Multicriterial and Parametric Network Flows Using a Pathological Graph of Zadeh,” Zeitschrift für Operations Research, Vol. 32, No. 1, 1988, pp. 9-27.
[4]	G. Ruhe, “Characterization of All Optimal Solutions and Parametric Maximal Flows in Networks,” Optimization, Vol. 16, No. 1, 1985, pp. 51-61. http://dx.doi.org/10.1080/02331938508842988
[5]	C.-E. Bichot and P. Siarry, “Graph Partitioning: Optimisation and Applications,” ISTE—Wiley, 2011.
[6]	E. Ciurea and L. Ciupala, “About Preflow Algorithms for the Minimum Flow Problem,” WSEAS Transactions on Computer Research, Vol. 1, No. 3, 2008, pp. 35-42.
[7]	E. Ciurea and L. Ciupala, “Sequential and Parallel Algorithms for Minimum Flows,” Journal of Applied Mathematics and Computing, Vol. 15, No. 1-2, 2004, pp. 53.E75.E.
[8]	G. Gallo, M. D. Grigoriadis and R. E. Tarjan, “A Fast Parametric Maximum Flow Algorithm and Applications,” SIAM Journal on Computing, Vol. 18, No. 1, 1989, pp. 30-55. http://dx.doi.org/10.1137/ 0218003
[9]	M. Parpalea, “Min-Max Algorithm for the Parametric Flow Problem,” Bulletin of the Transilvania University of Brasov, Series III: Mathematics, Informatics, Physics, Vol. 3, No. 52, 2010, pp. 191-198.