Applications of Network Flow Techniques

Shimon Even

doi:10.1017/CBO9781139015165.009

6 - Applications of Network Flow Techniques

Published online by Cambridge University Press: 05 June 2012

Shimon Even

Edited by

Guy Even

Show author details

Guy Even: Affiliation:
Tel-Aviv University

Book contents

Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'

Type: Chapter
Information: Graph Algorithms , pp. 117 - 145

DOI: https://doi.org/10.1017/CBO9781139015165.009 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] Even, S., Tarjan, R. E., “Network Flow and Testing Connectivity,” SIAM J. on comput., Vol. 4, 1975, pp. 507–518.CrossRef Google Scholar

[2] Menger, K., “Zur Aligemeinen Kurventheorie,” Fund. Math., Vol. 10, 1927, pp. 96–115.CrossRef Google Scholar

[3] Dantzig, G. B., Fulkerson, D. R., “On the Max-Flow Min-Cut Theorem of Networks,” Linear Inequalities and Related Systems, Annals of Math. Study 38, Princeton University Press, 1956, pp. 215–221.Google Scholar

[4] Hopcroft, J., and Tarjan, R. E., “Dividing a Graph into Triconnected Components”, SIAM J. on Comput., Vol. 2, 1973, pp. 135–158.CrossRef Google Scholar

[5] Kleitman, D. J., “Methods for Investigating Connectivity of Large Graphs,” IEEE Trans. on Circuit Theory, CT-16, 1969, pp. 232–233.Google Scholar

[6] Even, S., “Algorithm for Determining whether the Connectivity of a Graph is at Least k,” Siam J. on Comput., Vol. 4, 1977, pp. 393–396.Google Scholar

[7] Gomory, R. E., and Hu, T. C., “Multi-Terminal Network Flows,” J. of SIAM, Vol. 9, 1961, pp. 551–570.Google Scholar

[8] Schnorr, C. P., “Multiterminal Network Flow and Connectivity in Unsymmetrical Networks,” Department of Applied Math, University of Frankfurt, October 1977.Google Scholar

[9] Edmonds, J., “Edge-Disjoint Branchings,” in Combinatorial Algorithms, Courant Inst. Sci. Symp. 9, R., Rustin, Ed., Algorithmics Press Inc., 1973, pp. 91–96.Google Scholar

[10] Lovász, L., “On Two Minimax Theorems in Graph Theory,” Journal of Combinatorial Theory, Series B, Vol. 21:2, 1976, pp. 96–103.CrossRef Google Scholar

[12] Edmonds, J., “Paths, Trees, and Flowers,” Canadian J. of Math., Vol. 17, 1965, pp. 449–467.CrossRef Google Scholar

[13] Even, S., and Kariv, O., “An O(n2.5) Algorithmfor MaximumMatching in General Graphs,” 16th Annual Symposium on Foundations of Computer Science, IEEE, 1975, pp. 100–112.

[14] Hopcroft, J., and Karp, R. M., “An O(n5/2) Algorithm for Maximum Matching in Bipartite Graphs,” SIAM J. on Comput., 1975, pp. 225–231.

[15] Hall, P., “On Representation of Subsets,” J. London Math. Soc. Vol. 10, 1935, pp. 26–30.Google Scholar

[16] Dilworth, R. P., “A Decomposition Theorem for Partially Ordered Sets,” Ann. Math., Vol. 51, 1950, pp. 161–166.CrossRef Google Scholar