%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%								    									%
% This file contains 						    						%
%								    									%
%		A Bibliography on Network Flow Problems		    				%
%								    									%
%			Marinus Veldhorst			    							%
%	Department of Computer Science,	 University of Utrecht	    		%
%	  P.O. Box 80.089, 3508 TB  Utrecht, The Netherlands.	    		%
%	email:  marinus\at\cs.ruu.nl	    	    						%
%								    									%
% The work for compiling this bibliography was partially supported  	%
% by the  ESPRIT II Basic Research Actions Program of the EC under  	%
% contract no. 3075 (project ALCOM).  This  bibliography  has been  	%
% published in the Newsletter of ALCOM:  Algorithms Review, vol. 1  	%
% (1990), pp. 97-117.						    						%
% The  author grants  permission to make  any number of  copies of  	%
% this file.  Other  changes  to the file  or any of its copies or  	%
% copying parts of the file are  allowed only after  permission is 		%
% obtained from the author.  Copies on paper must be made from the  	%
% publication in Algorithms Review.				    					%
%								    									%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@string{jalg = "J. Algor."}
@string{jpdc = "J. Parallel Distrib. Comput."}
@string{focs = "Annual IEEE Symp. Found. of Computer Science"}
@string{lncs = "Lecture Notes in Computer Science, vol. "}
@string{stoc = "Annual ACM Symp. Theory of Computing"}
@string{siam = "Society for Industrial and Applied Math."}
@string{opres = "Oper. Res."}
@string{DCSU = "Dept. of Computer Science, University of "}
@string{DCS = "Dept. of Computer Science"}

@article{kn:AhujaBatraGup84 ,
	title = "A parametric algorithm for the convex cost network
		flow and related problems" ,
	author = "Ahuja, Ravindra K.  and J. L. Batra and S. K. Gupta" ,
	journal= "Europ. J. of Oper. Res." ,
	volume = 16 ,
	year = 1984 ,
	pages = "222--235"	}

@techreport{kn:AhujaGoldbOrTar88 ,
	title = "Finding minimum-cost flows by double scaling" ,
	author = "Ahuja, Ravindra K.  and  Andrew V. Goldberg  and
		James B. Orlin  and  Robert E. Tarjan" ,
	number = "STAN-CS-88-1227" ,
	institution = DCS # ", Stanford University" ,
	year = 1988	}

@techreport{kn:AhujaOrlin88 ,
	title = "Improved primal simplex algorithms for the shortest
		path, assignment and minimum cost flow problems" ,
	author = "Ahuja, Ravindra K.  and  James B. Orlin" ,
	number = "2090-88" ,
	institution = "Sloan School of Management, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1988	}

@unpublished{kn:AhujaOrStTar88 ,
	title = "Improved algorithms for bipartite network flow
		problems" ,
	author = "Ahuja, Ravindra K.  and  James B. Orlin  and
		C. Stein  and  Robert E. Tarjan" ,
	note = "To appear"	}

@incollection{kn:AhujaMagnOrlin89 ,
	title = "Network flows" ,
	author = "Ahuja, Ravindra K.  and  T. L. Magnanti  and
		James B. Orlin" ,
	publisher = "North Holland Publ. Comp." ,
	address = "Amsterdam" ,
	year = 1989 ,
	booktitle = "Handbooks of Operations Research and Management
		Science, vol. 1: Optimization" ,
	editor = "G. L. Nemhauser  and  A. H. G. {Rinnooy Kan}  and
		 M. J. Todd"	}

@article{kn:AhujaOrlin89,
	title = "A fast and simple algorithm for the maximum flow
		problem",
	author = "Ahuja, Ravindra K.  and  James B. Orlin" ,
	journal= opres ,
	volume = 37 ,
	year = 1989 ,
	pages = "748--759"	}

@article{kn:AhujaOrlinTarjan89 ,
	title = "Improved time bounds for the maximum flow problem",
	author = "Ahuja, Ravindra K.  and  James B. Orlin  and
		Robert E. Tarjan" ,
	journal= sicomp ,
	volume = 18 ,
	year = 1989,
	pages = "939--954"	}

@article{kn:AliBFKPSMW84 ,
	title = "Multicommodity network problems: {A}pplications and
		computations" ,
	author = "Ali, I.  and D. Barnett  and  K. Farhangian and
		J. Kennington  and  B. Patty  and  B. Shetty  and
		B. McCarl and  P. Wong" ,
	journal= "A.I.I.E. Trans." ,
	volume = 16 ,
	year = 1984 ,
	pages = "127--134"	}

@article{kn:AliPadmanThiag89,
	title = "Dual algorithms for pure network problems",
	author = "Ali, Agha Iqbal  and  Rema Padman  and  Hemalatha
		Thiagaran" ,
	journal= opres ,
	volume = 37 ,
	year = 1989 ,
	pages = "159--171"	}

@article{kn:ArlinPapad86 ,
	title = "On the complexity of circulations" ,
	author = "Arlin, Esther M. and Papadimitriou, Christos H. ",
	journal= jalg ,
	volume = 7 ,
	year = 1986,
	pages = "134--145"	}

@article{kn:Assad78 ,
	title = "Multicommodity network flows - A survey" ,
	author = "Assad, A." ,
	journal= "Networks" ,
	volume = 8 ,
	year = 1978,
	pages = "37--91"	}

@article {kn:Awerbuch85 ,
	title = "Reducing complexities of the distributed max-flow and
		breadth-first-search algorithms by means of network
		synchronization" ,
	author = "Baruch Awerbuch" ,
	journal = "Networks" ,
	volume = 15 ,
	year = 1985 ,
	pages = "425--437"	}

@article{kn:BarahonaTardos89 ,
	title = "Note on {W}eintraub's minimum-cost circulation
		algorithm" ,
	author = "Francisco Barahona  and {\'{E}} Tardos" ,
	journal= sicomp ,
	volume = 18 ,
	year = 1989,
	pages = "579--583"	}

@techreport{kn:Baratz80 ,
	title = "The complexity of maximum network flow" ,
	author = "Baratz, A. E." ,
	institution = "Lab. for Computer Science, MIT" ,
	address = "Cambridge, Mass." ,
	number = "MIT/LCS/TR-230" ,
	year = 1980	}

@book{kn:BazaraaJarvis78 ,
	title = "Linear Programming and Network Flows" ,
	author = "Bazaraa, M.  and  J. J. Jarvis" ,
	publisher = "John Wiley \& Sons" ,
	address = "New York" ,
	year = 1978	}

@article{kn:BellmanVemu73 ,
	title = "On multicommodity maximal dynamic flows" ,
	author = "Bellmore, M.  and  R. R. Vemuganti" ,
	journal= opres ,
	volume = 21 ,
	year = 1973,
	pages = "10--21"	}

@article{kn:Benington73 ,
	title = "An efficient minimal cost flow algorithm" ,
	author = "Bennington, G. E." ,
	journal= "Manag. Sci." ,
	volume = 19 ,
	year = 1973,
	pages = "1042--1051"	}

@book {kn:BergeGhouil62 ,
	title = "Programming, Games and Transportation Networks" ,
	author = "Berge, C.  and  A. Ghouila-Houri" ,
	publisher = "John Wiley \& Sons" ,
	address = "New York" ,
	year = 1962	}

@inbook {kn:Berge73 ,
	title = "Graphs and Hypergraphs" ,
	author = "Berge, C" ,
	chapter = 5 ,
	publisher = "North Holland Publ. Comp." ,
	address = "Amsterdam" ,
	year = 1973	}

@article{kn:Bertsekas85 ,
	title = "A unified framework for primal-dual methods in
		minimum cost network flow problems" ,
	author = "Bertsekas, Dimitri P." ,
	journal= "Math. Progr." ,
	volume = 32 ,
	year = 1985,
	pages = "125--145"	}

@techreport {kn:Bertsekas86 ,
	title = "Distributed asynchronous relaxation methods for linear
		network flow problems" ,
	author = "Bertsekas, D. P." ,
	institution = "Lab. for Decision Systems, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1986 ,
	number = "LIDS-P-1986"	}

@article{kn:BertsBaz87 ,
	title = "Distributed asynchronous relaxation methods for convex
		network flow problems" ,
	author = "Bertsekas, Dimitri P.  and  D. {El Baz}" ,
	journal= "SIAM J. Contr. \& Optim." ,
	volume = 25 ,
	year = 1987,
	pages = "74--85"	}

@article{kn:BertsHosTs87 ,
	title = "Relaxation methods for network flow problems with
		convex arc costs" ,
	author = "Bertsekas, Dimitri P  and  P. A. Hosein  and
		P. Tseng" ,
	journal= "SIAM J. Contr. \& Optim." ,
	volume = 25 ,
	year = 1987,
	pages = "1219--1243"	}

@article{kn:BertsEckst88 ,
	title = "Dual coordinate step methods for linear network
		flow problems" ,
	author = "Bertsekas, Dimitri P.  and  J. Eckstein" ,
	journal= "Math. Progr." ,
	volume = 42 ,
	year = 1988,
	pages = "203--243"	}

@inproceedings{kn:BertsTseng88a ,
	title = "The relax codes for linear minimum cost network
		flow problems" ,
	author = "Bertsekas, Dimitri P  and  P. Tseng" ,
	booktitle = "FORTRAN Codes for Network Optimization" ,
	editor = "{B. Simeone, et al.}" ,
	series = "Annals of Operations Research, vol. 13, pages
		125--190" ,
	year = 1988	}

@article{kn:BertsTseng88b ,
	title = "Relaxation methods for minimum cost ordinary and
		generalized network flow problems" ,
	author = "Bertsekas, Dimitri P.  and  P. Tseng" ,
	journal= opres ,
	volume = 36 ,
	year = 1988 ,
	pages = "93--114"	}

@inbook {kn:BertsekasTsitsiklis89 ,
	title = "Parallel and Distributed Computation" ,
	author = "Dimitri P. Bertsekas  and  John N. Tsitsiklis" ,
	chapter = "5, 6.5 and 6.6" ,
	publisher = "Prentice-Hall" ,
	address = "Englewood Cliffs, NJ" ,
	year = 1989	}

@techreport {kn:BlandJensen85 ,
	title = "On the computational behavior of a polynomial-time
		network flow algorithm" ,
	author = "Bland, R. G.  and  D. L. Jensen" ,
	institution = "School of Operations Research and Industrial
		Engineering, Cornell University" ,
	address = "Ithaca, NY" ,
	year = 1985 ,
	number = 661	}

@article{kn:BradlBrGr77 ,
	title = "Design and implementation of large scale primal
		transshipment algorithms" ,
	author = "Bradley, G.  and  G. Brown  and  G. Graves" ,
	journal= "Manag. Sci." ,
	volume = 24 ,
	year = 1977,
	pages = "1--38"	}

@book{kn:BradlHaxMagn77 ,
	title = "Applied Mathematical Programming" ,
	author = "Bradley, S. P.  and  A. C. Hax  and T. L.  Magnanti" ,
	publisher = "Addison-Wesley Publ. Comp." ,
	address = "New York" ,
	year = 1977	}

@misc{kn:BusackerGow61 ,
	title = "A procedure for determining a family of minimal-cost
		network flow patterns" ,
	author = "Busacker, R. G.  and  P. J. Gowen" ,
	howpublished = "O.R.O. Technical paper 15, Johns Hopkins
		University, Baltimore, MD" ,
	year = 1961	}

@book{kn:BusackerSaaty65 ,
	title = "Finite Graphs and Networks: An Introduction with
		Applications" ,
	author = "Busacker, R G  and  T L Saaty" ,
	publisher = "McGraw-Hill" ,
	address = "New York" ,
	year = 1965	}

@inproceedings {kn:ChenFeng73 ,
	title = "A parallel algorithm for maximum flow problem",
	author = "Chen, I. N. and T. Y. Feng",
	booktitle = "Proc. 1973 Sagamore Computer Conf. " ,
	year = 1973	}

@inproceedings {kn:Chen74 ,
	title = "A new parallel algorithm for network flow problems",
	author = "Chen, I. N. ",
	booktitle = "Proc. 1974 Sagamore Computer Conf. " ,
	editor = "Feng, T. Y." ,
	series = lncs # "24" ,
	address = "Springer-Verlag, Berlin" ,
	year = 1975 ,
	pages = "306--307"	}

@article{kn:ChenChenFeng79 ,
	title = "Associative processing of network flow problems" ,
	author = "Chen, I. N. and  P. Y. Chen and T. Y. Feng",
	journal= ieeetc ,
	volume = "C-28" ,
	year = 1979,
	pages = "184--190"	}

@techreport{kn:ChengHu88 ,
	title = "Maximum concurrent flow and minimum ratio cut" ,
	author = "Cheng, C. K.  and  T. C. Hu" ,
	number = "CS88-141" ,
	institution = "University of California" ,
	address = "San Diego, CA" ,
	month = dec ,
	year = 1988 }

@techreport{kn:Cheriyan88 ,
	title = "Parametrized worst case networks for preflow push
		algorithms" ,
	author = "Cheriyan, Joseph" ,
	institution = "Computer Science Group, Tata Institute of
		Fundamental Research" ,
	address = "Bombay, India" ,
	year = 1988	}

@article{kn:CheriyanMaheshw89a ,
	title = "Analysis of preflow push algorithms for maximum
		network flow" ,
	author = "Cheriyan, Joseph  and  S. N. Maheshwari" ,
	journal= sicomp ,
	volume = 18 ,
	year = 1989,
	pages = "1057--1086"	}

@article{kn:CheriyanMaheshw89b ,
	title = "The parallel complexity of finding a blocking flow in a
		3-layer network" ,
	author = "Cheriyan, Joseph  and  S. N. Maheshwari" ,
	journal= ipl ,
	volume = 31 ,
	year = 1989,
	pages = "157--161"	}

@inproceedings {kn:CheriyanHagerup89 ,
	title = "A randomized maximum-flow algorithm" ,
	author = "Cheriyan, Joseph  and  Torben Hagerup" ,
	booktitle = "Proc. 30th " # focs ,
	year = 1989 ,
	pages = "118--123"	}

@inproceedings {kn:CherHagerMehlh90 ,
	title = "Can a maximum flow be computed in $o(nm)$ time?" ,
	author = "Cheriyan, Joseph  and  Torben Hagerup  and  Kurt
		Mehlhorn" ,
	booktitle = "Proc. 17th ICALP" ,
	year = 1990,
	note = "To appear"	}

@article{kn:Cherkasky77 ,
	title = "Algorithm of construction of maximal flow in
		networks with complexity of ${O}({V}^{2}\sqrt{{E}})$
		operations" ,
	author = "Cherkasky, R. V." ,
	journal= "Math. Methods of Solution of Economical Problems" ,
	volume = 7 ,
	year = 1977,
	pages = "112--125" ,
	note = "(In Russian)"	}

@article{kn:Cheung80 ,
	title = "Computational comparison of eight methods for the
		maximum network flow problem" ,
	author = "Cheung, T." ,
	journal= toms ,
	volume = 6 ,
	year = 1980,
	pages = "1--16" }

@article{kn:Cheung83 ,
	title = "Graph traversal techniques and the maximum flow problem
		in distributed computation" ,
	author = "Cheung, T." ,
	journal= ieeese ,
	volume = "SE-9" ,
	year = 1983,
	pages = "504--512" }

@inbook {kn:Christofides75 ,
	title = "Graph Theory: {A}n Algorithmic Approach" ,
	author = "Christofides, N." ,
	chapter = 11 ,
	publisher = "Academic Press" ,
	address = "New York" ,
	year = 1975	}

@inbook {kn:CormenLeisRivest90 ,
	title = "Introduction to Algorithms" ,
	author = "Thomas H. Cormen  and  Charles E. Leiserson  and
		Ronald L. Rivest" ,
	chapter = 28 ,
	publisher = "MIT Press" ,
	address = "Cambridge, Mass." ,
	year = 1990	}

@article{kn:Cui88 ,
	title = "A network simplex method for the maximum balanced flow
		problem" ,
	author = "Wentian Cui" ,
	journal = "J. Oper. Res. Soc. Japan" ,
	volume = 31 ,
	year = 1988,
	pages = "551--563"	}

@article{kn:Cunningham76 ,
	title = "A network simplex method" ,
	author = "Cunningham, W. H." ,
	journal= "Math. Progr." ,
	volume = 11 ,
	year = 1976,
	pages = "105--116"	}

@article{kn:Cunningham79 ,
	title = "Theoretical properties of the network simplex method" ,
	author = "Cunningham, W. H." ,
	journal= "Math. Oper. Res." ,
	volume = 4 ,
	year = 1979,
	pages = "196--208"	}

@article{kn:CunninghamFrank85 ,
	title = "A primal-dual algorithm for submodular flows" ,
	author = "Cunningham, W. H.  and  A. Frank" ,
	journal= "Math. Oper. Res." ,
	volume = 10 ,
	year = 1985,
	pages = "251--262"	}

@inproceedings {kn:Dantzig51 ,
	title = "Application of the simplex method to a transportation
		problem" ,
	author = "Dantzig, G. B." ,
	booktitle = "Activity Analysis of Production and Allocation" ,
	editor = "Koopmans, T. C." ,
	address = "J. Wiley \& Sons, New York" ,
	year = 1951 ,
	pages = "359--373"	}

@inproceedings {kn:DantzFulk56 ,
	title = "On the max-flow min-cut theorem of networks" ,
	author = "Dantzig, G. B.  and  D. R. Fulkerson" ,
	booktitle = "Linear Inequalities and Related Systems" ,
	editor = "Kuhn, H. W.  and  A. W. Tucker" ,
	series = "Annals of Mathematics Study, vol. 38, pages
		215--221" ,
	address = "Princeton Univ. Press, Princeton, NJ" ,
	year = 1956	},

@book{kn:Dantzig62 ,
	title = "Linear Programming and Extensions" ,
	author = "Dantzig, G. B." ,
	publisher = "Princeton Univ. Press" ,
	address = "Princeton, NJ" ,
	year = 1962	}

@book{kn:Derigs88 ,
	title = "Programming in Networks and Graphs" ,
	author = "Derigs, U." ,
	series = "Lecture Notes in Economics and Mathematical Systems,
		vol. 300" ,
	publisher = "Springer-Verlag" ,
	address = "Berlin" ,
	year = 1988	}

@article{kn:DerigsMeier89 ,
	title = "Implementing Goldberg's max-flow algorithm, a
		computational investigation" ,
	author = "Derigs, U.  and  W. Meier" ,
	journal= "Z. Oper. Res." ,
	volume = 33 ,
	year = 1989,
	pages = "383--403"	}

@article{kn:Dinic70 ,
	title = "Algorithm for solution of a problem of maximum flow
		in networks with power estimation" ,
	author = "Dinic, E. A." ,
	journal= "Soviet Math. Dokl." ,
	volume = 11 ,
	year = 1970,
	pages = "1277--1280"	}

@article{kn:EdmondsKarp72 ,
	title = "Theoretical improvements in algorithmic efficiency for
		network flow problems" ,
	author = "Edmonds, Jack  and  Richard M. Karp" ,
	journal= jacm ,
	volume = 19 ,
	year = 1972,
	pages = "248--264"	}

@article{kn:ElamGlovKl79 ,
	title = "A strongly convergent primal simplex algorithm
		for generalized networks" ,
	author = "Elam, J.  and  F. Glover  and  D. Klingman" ,
	journal= "Math. Oper. Res." ,
	volume = 4 ,
	year = 1979,
	pages = "39--59"	}

@article{kn:EliasFeinstShan56 ,
	title = "A note on the maximum flow through a network" ,
	author = "Elias, P.  and  A. Feinstein  and  C. E. Shannon" ,
	journal= "IEEE Trans. Inform. Th." ,
	volume = "IT-2" ,
	year = 1956,
	pages = "117--119"	}

@article{kn:Elmaghraby64 ,
	title = "Sensitivity analysis of multi-terminal network flows" ,
	author = "Elmaghraby, S. E." ,
	journal= "J. ORSA" ,
	volume = 12 ,
	year = 1964,
	pages = "680--688"	}

@article{kn:EngelSchneid75 ,
	title = "Diagonal similarity and equivalence for matrices over
		groups with 0" ,
	author = "Engel, G M  and  H Schneider" ,
	journal= "Czech. Math. J." ,
	volume = 25 ,
	year = 1975,
	pages = "389--403"	}

@article{kn:EvenTarjan75 ,
	title = "Network flow and testing graph connectivity" ,
	author = "Shimon Even and Robert E. Tarjan" ,
	journal= sicomp ,
	volume = 4 ,
	year = 1975,
	pages = "507--518"	}

@article{kn:EvenItaiShamir76 ,
	title = "On the complexity of timetable and multicommodity
		flow problems",
	author = "Shimon Even  and  Alon Itai  and  A. Shamir",
	journal= sicomp ,
	volume = 5 ,
	year = 1976,
	pages = "691--703"	}

@techreport{kn:Even76 ,
	title = "The max-flow algorithm of {D}inic and {K}arzanov.
		{A}n exposition" ,
	author = "Shimon Even" ,
	number = "MIT/LCS/TM-80" ,
	institution = "Lab. for Computer Science, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1976	}

@inbook {kn:Even79 ,
	title = "Graph Algorithms" ,
	author = "Shimon Even" ,
	chapter = "4, 5, and 10.8" ,
	publisher = "Pitman Publ. Lmtd" ,
	address = "London" ,
	year = 1979	}

@article{kn:FernandezMartel89 ,
	title = "On the efficiency of maximum-flow algorithms on
		networks with small integer capacities" ,
	author = "Fernandez-Baca, David  and Charles U. Martel",
	journal= "Algorithmica" ,
	volume = 4 ,
	year = 1989,
	pages = "173--189"	}

@article{kn:FordFulk56 ,
	title = "Maximal flow through a network" ,
	author = "Ford, L. R.  and  D. R. Fulkerson" ,
	journal= "Canad. J. Math." ,
	volume = 8 ,
	year = 1956,
	pages = "399--404"	}

@article{kn:FordFulk58a ,
	title = "A suggested computation for maximal multicommodity
		network flow" ,
	author = "Ford, L. R.  and  D. R. Fulkerson" ,
	journal= "Manag. Sci." ,
	volume = 5 ,
	year = 1958,
	pages = "97--101"	}

@article{kn:FordFulk58b ,
	title = "Constructing maximal dynamic flows from static flows" ,
	author = "Ford, L. R.  and  D. R. Fulkerson" ,
	journal= opres ,
	volume = 6 ,
	year = 1958,
	pages = "419--433"	}

@article{kn:FordFulk59 ,
	title = "A network flow feasibility theorem and combinatorial
		applications" ,
	author = "Ford, L. R.  and  D. R. Fulkerson" ,
	journal= "Canad. J. Math." ,
	volume = 11 ,
	year = 1959,
	pages = "440--450"	}

@book{kn:FordFulk63 ,
	title = "Flows in Networks",
	author = "Ford, L. R. and D. R. Fulkerson" ,
	publisher = "Princeton Univ. Press" ,
	address = "Princeton, NJ" ,
	year = 1973	}

@inproceedings {kn:FrankTardos85 ,
	title = "An applications of simultaneous approximations in
		combinatorial optimization",
	author = "Frank, A. and {\'{E}} Tardos",
	booktitle = "Proc. 26th " # focs ,
	year = 1985 ,
	pages = "459--463"	}

@book{kn:FrankFrisch71 ,
	title = "Communication, Transmission, and Transportation
		networks" ,
	author = "Frank, H.  and  I. T. Frisch" ,
	publisher = "Addison-Wesley Publ. Comp." ,
	address = "New York" ,
	year = 1971	}

@article{kn:Frederickson87 ,
	title = "Fast algorithms for shortest paths in planar graphs,
		with applications" ,
	author = "Frederickson, Greg N. " ,
	journal= sicomp ,
	volume = 16 ,
	year = 1987,
	pages = "1004--1022"	}

@inproceedings {kn:Fujisawa63 ,
	title = "Maximal flow in a lossy network" ,
	author = "Fujisawa, T." ,
	booktitle = "Proc. Allerton Conf. on Circuit and System
		Theory" ,
	year = 1963 ,
	pages = "385--393"	}

@article {kn:Fujishige86 ,
	title = "A capacity-rounding algorithms for the minimum-cost
		circulation problem: a dual framework of the {T}ardos
		algorithm" ,
	author = "Fujishige, Satoru" ,
	journal = "Math. Progr." ,
	volume = 35 ,
	year = 1986 ,
	pages = "298--308"	}

@article {kn:FujishigeNakaCui86 ,
	title = "On the equivalence of the maximum balanced flow
		problem amd the weighted minimax flow problem" ,
	author = "Fujishige, S.  and  A. Nakayama  and  W-T. Cui" ,
	journal = opres # " Lett." ,
	volume = 5 ,
	year = 1986 ,
	pages = "207--209"	}

@article{kn:FulkDantz55 ,
	title = "Computation of maximum flow in networks" ,
	author = "Fulkerson, D. R.  and  G. B. Dantzig" ,
	journal= "Naval Res. Log. Quart." ,
	volume = 2 ,
	year = 1955,
	pages = "277--283"	}

@article{kn:Fulk61 ,
	title = "An out-of-kilter method for minimal cost flow
		problem" ,
	author = "Fulkerson, D. R." ,
	journal= "SIAM J. Appl. Math." ,
	volume = 9 ,
	year = 1961,
	pages = "18--27"	}

@article{kn:Gabow85 ,
	author = "Gabow, Harold N." ,
	title = "Scaling algorithms for network problems" ,
	journal= jcss ,
	volume = 31 ,
	year = 1985,
	pages = "148--168"	}

@article{kn:GabowTarjan89 ,
	author = "Gabow, Harold N.  and  Robert E. Tarjan" ,
	title = "Faster scaling algorithms for network problems" ,
	journal= sicomp ,
	volume = 18 ,
	year = 1989,
	pages = "1013--1036"	}

@article{kn:Galil80 ,
	author = "Zvi Galil" ,
	title = "An ${O}( n^{5/3} m^{2/3} )$ algorithm for the
		maximal flow problem",
	journal= acta ,
	volume = 14 ,
	year = 1980,
	pages = "221--242",
	note = "Preliminary version in Proc. 19th " # focs # ", pages
		231--245, 1978"	}

@article{kn:GalilNaamad80 ,
	author = "Zvi Galil and Amnon Naamad" ,
	title = "An ${O}({EV} \log ^{2} {V})$ algorithm for the maximal
		flow problem" ,
	journal= jcss ,
	volume = 21 ,
	year = 1980,
	pages = "203--217"	}

@article{kn:Galil81 ,
	author = "Zvi Galil" ,
	title = "On the theoretical efficiency of various network flow
		algorithms" ,
	journal= tcs ,
	volume = 14 ,
	year = 1981,
	pages = "103--111"	}

@article {kn:GalilTardos88 ,
	title = "An ${O}(n^{2} (m+ n \log n ) \log n)$ min-cost flow
		algorithm" ,
	author = "Galil, Zvi  and  {\'{E}}. Tardos" ,
	journal = jacm ,
	note = "Preliminary version in Proc. 27th " # focs # ", pages
		1--9, 1986" ,
	year = 1988 ,
	pages = "374--386"	}

@article{kn:GalloGrigoriadisTarjan89 ,
	author = "Giorgio Gallo  and  Michael D. Grigoriadis  and
		Robert E. Tarjan " ,
	title = "A fast parametric maximum flow algorithm and
		applications" ,
	journal= sicomp ,
	volume = 18 ,
	year = 1989,
	pages = "30--55"	}

@inbook {kn:GareyJohnson79 ,
	title = "Computers and Intractibility, a Guide to the Theory
		of NP-Completeness" ,
	author = "Garey, Michael R.  and  David S. Johnson" ,
	chapter = "A2" ,
	publisher = "W.H. Freeman and Co." ,
	address = "San Francisco" ,
	year = 1979	}

@article{kn:GloverKarnKl74 ,
	title = "Implementation and computational comparisons of
		primal, dual and primal-dual computer codes for
		minimum cost network flow problem" ,
	author = "Glover, F.  and  D. Karney  and  D. Klingman" ,
	journal= "Networks" ,
	volume = 4 ,
	year = 1974,
	pages = "191--212"	}

@article{kn:GloverKarnKlNap74 ,
	title = "A computational study on start procedures, basis
		change criteria, and solution algorithms for
		transportation problem" ,
	author = "Glover, F.  and  D. Karney  and  D. Klingman
		and  A. Napier" ,
	journal= "Manag. Sci." ,
	volume = 20 ,
	year = 1974,
	pages = "793--813"	}

@techreport {kn:Goldberg85 ,
	title = "A new max-flow algorithm" ,
	author = "Goldberg, Andrew V." ,
	institution = "Lab. for Computer Science, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1985 ,
	number = "MIT/LCS/TM-291"	}

@phdthesis {kn:Goldberg87 ,
	title = "Efficient graph algorithms for sequential and parallel
		computers" ,
	author = "Andrew V. Goldberg" ,
	school = "Dept. of Electr. Engin. and Computer Science, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1987 ,
	note = "Also available als Technical Report TR-374, Lab. for
		Computer Science, MIT, Cambridge, Mass., 1987"	}

@inproceedings {kn:GoldbergTarjan87a ,
	title = "Solving minimum-cost flow problems by successive
		approximation",
	author = "Andrew V. Goldberg  and  Robert E. Tarjan" ,
	booktitle = "Proc. 19th " # stoc ,
	year = 1987 ,
	pages = "7--18"	}

@techreport {kn:GoldbergTarjan87b ,
	title = "Finding minimum-cost circulations by successive
		approximation" ,
	author = "Goldberg, Andrew V.  and  Robert E Tarjan" ,
	institution = "Lab. for Computer Science, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1987 ,
	number = "MIT/LCS/TM-333" ,
	note = "Math. Oper. Res., to appear"	}

@article{kn:GoldbergTarjan88 ,
	title = "A new approach to the maximum flow problem" ,
	author = "Andrew V. Goldberg  and  Robert E. Tarjan" ,
	journal = jacm ,
	volume = 35 ,
	year = 1988 ,
	pages = "921-940" ,
	note = "Preliminary version in Proc. 18th " # stoc # ", pages
		136--146, 1986"	}

@techreport {kn:GoldbergPlotkTard88 ,
	title = "Combinatorial algorithms for the generalized
		circulation problem" ,
	author = "Andrew V. Goldberg  and  S. A. Plotkin  and
		{\'{E}} Tardos" ,
	institution = DCS # ", Stanford University" ,
	month = jun ,
	year = 1988 ,
	number = "STAN-CS-88-1209" ,
	note = "Also available as Technical Memorandum MIT/LCS/TM-358,
		Lab. for Computer Science, MIT, Cambridge, Mass., 1988"
        }

@techreport {kn:GoldbergTardTarj89 ,
	title = "Network flow algorithms" ,
	author = "Andrew V. Goldberg  and  {\'{E}} Tardos  and
		Robert E. Tarjan" ,
	institution = DCS # ", Stanford University" ,
	month = mar ,
	year = 1989 ,
	number = "STAN-CS-89-1252"	}

@article{kn:GoldbergTarjan89a ,
	author = "Andrew V. Goldberg  and  Robert E. Tarjan" ,
	title = "A parallel algorithm for finding a blocking flow
		in an acyclic network" ,
	journal= ipl ,
	volume = 31 ,
	year = 1989,
	pages = "265--271"	}

@article {kn:GoldbergTarjan89b ,
	title = "Finding minimum-cost circulations by canceling
		negative cycles" ,
	author = "Andrew V. Goldberg  and  Robert E. Tarjan" ,
	journal = jacm ,
	volume = 36 ,
	year = 1989 ,
	pages = "873--886",
	note = "Preliminary version in Proc. 20th " # stoc # ", pages
		388--397, 1987"	}

@techreport{kn:GoldbergGrigorTarjan90,
	author = "Goldberg, Andrew V.  and  M. D. Grigoriadis  and
		Robert E. Tarjan " ,
	title = "Efficiency of the network simplex algorithm for the
		maximum flow problem" ,
	number = "STAN-CS-89-1248",
	institution = DCS # ", Stanford University" ,
	address = "Stanford, CA" ,
	note = "To appear in {\em Math. Progr.}" }

@article{kn:GoldenMagn77 ,
	title = "Deterministic network optimization: {A} bibliography" ,
	author = "Golden, B.  and  T. L. Magnanti" ,
	journal= "Networks" ,
	volume = 7 ,
	year = 1977,
	pages = "149--183"	}

@inproceedings{kn:GoldfGrigo86 ,
	title = "A computational comparison of the {D}inic and network
		simplex methods for maximum flow" ,
	author = "Goldfarb, D.  and  M. D. Grigoriadis" ,
	booktitle = "FORTRAN Codes for Network Optimization" ,
	editor = "{B. Simeone, et al.}" ,
	series = "Annals of Operations Research, vol. 13, pages
		83--124" ,
	year = 1988	}

@techreport{kn:GoldfarbHao88 ,
	title = "A primal simplex algorithm that solves the
		maximum flow problem in at most ${O}(nm)$ pivots and
		${O}(n^{2}m)$ time" ,
	author = "D. Goldfarb  and J. Hao" ,
	number = "" ,
	institution = "Dept. of Industrial Engineering and Operations
		Research, Columbia University" ,
	address = "New York" ,
	year = 1988 }

@article{kn:GoldfHaoKai90 ,
	title = "Anti-stalling pivot rules for the network simplex
		algorithm", 
	author = "Goldfarb, D. and  J. Hao  and  S. Kai" ,
	journal= "Networks" ,
	volume = 20 ,
	year = 1990,
	pages = "79--91"	}

@article{kn:GoldschlShawStaples82 ,
	author = "Leslie M. Goldschlager  and  Ralph A. Shaw and
		John Staples" ,
	title = "The maximum flow problem is log space complete
		for {P}" ,
	journal= tcs ,
	volume = 21 ,
	year = 1982,
	pages = "105--111" ,
	note = "\\ See also T. Lengauer and K. W. Wagner, The correlation
		between the complexities of non-hierarchical and
		hierarchical versions of graph problems.  In:
		F. J. Brandenburg, G. Vidal-Nacquet and M. Wirsing
		(eds.), Proc. STACS 87 -- 4th Annual Symp. on Theor.
		Aspects of Computer Science, " # lncs # "247, pages
		100--113, Springer-Verlag, Berlin, 1987"
		}

@article{kn:GomoryHu61 ,
	title = "Multi-terminal network flows" ,
	author = "Gomory, R. E.  and  T. C. Hu" ,
	journal= "J. SIAM" ,
	volume = 9 ,
	year = 1961,
	pages = "551--570"	}

@article{kn:GomoryHu62 ,
	title = "An application of generalized linear programming to
		network flows" ,
	author = "Gomory, R. E.  and  T. C. Hu" ,
	journal= "J. SIAM" ,
	volume = 10 ,
	year = 1962,
	pages = "260--283"	}

@article{kn:GomoryHu64 ,
	title = "Synthesis of a communication network" ,
	author = "Gomory, R. E.  and  T. C. Hu" ,
	journal= "J. SIAM" ,
	volume = 12 ,
	year = 1964,
	pages = "348--369"	}

@inbook {kn:GondranMinoux84 ,
	title = "Graphs and Algorithms" ,
	author = "Gondran, M.  and  M. Minoux" ,
	chapter = "5 and 6" ,
	publisher = "Wiley-Interscience" ,
	address = "New York" ,
	year = 1984	}

@article{kn:GranotVeinot85 ,
	title = "Substitutes, complements and ripples in network
		flows" ,
	author = "Granot, Frieda  and Arthur F. {Veinott Jr}" ,
	journal= "Math. Oper. Res." ,
	volume = 10 ,
	year = 1985,
	pages = "471--497"	}

@article{kn:GranotHass86 ,
	title = "Multi-terminal maximum flows in node capacitated
		networks" ,
	author = "Granot, Frieda  and R. Hassin" ,
	journal= "Discrete Appl. Math." ,
	volume = 13 ,
	year = 1986,
	pages = "157--163"	}

@article {kn:GrigoriadisWh72 ,
	title = "A partitioning algorithm for the multicommodity
		network flow problem" ,
	author = "Grigoriadis, M. D.  and  W. W. White" ,
	journal = "Math. Progr." ,
	volume = 3 ,
	year = 1972 ,
	pages = "157--177"	}

@article {kn:Grigoriadis86 ,
	title = "An efficient implementation of the network simplex
		method" ,
	author = "Grigoriadis, M. D." ,
	journal = "Math. Prog. Study" ,
	volume = 26 ,
	year = 1986 ,
	pages = "83--111"	}

@article{kn:GrimmettWelsh82 ,
	title = "Flow in networks with random capacities" ,
	author = "Grimmett, G. R.  and  D. J. A. Welsh" ,
	journal= "Stochastics" ,
	volume = 7 ,
	year = 1982,
	pages = "205--229"	}

@article{kn:GrimmettSuen82 ,
	title = "The maximal flow through a directed graph with
		random capacities" ,
	author = "Grimmett, G. R.  and  W-C. S. Suen" ,
	journal= "Stochastics" ,
	volume = 8 ,
	year = 1982,
	pages = "153--159"	}

@article{kn:Grinold73 ,
	title = "Calculating maximal flows in a network with positive
		gains" ,
	author = "Grinold, R. C. " ,
	journal= opres ,
	volume = 21 ,
	year = 1973,
	pages = "528--541"	}

@book {kn:GrotschelLovSchrijv88 ,
	title = "Geometric Algorithms and Combinatorial Optimization" ,
	author = "Gr{\"{o}}tschel, M  and  L {Lov\'{a}sz}  and  A.
		Schrijver" ,
	publisher = "Springer-Verlag" ,
	address = "Berlin" ,
	year = 1988	}

@article{kn:Gupta66 ,
	author = "Gupta, R. P." ,
	title = "On flows in pseudosymmetric networks" ,
	journal= "J. SIAM" ,
	volume = 14 ,
	year = 1966,
	pages = "215--225"	}

@article{kn:Gusfield83 ,
	author = "Gusfield, Dan" ,
	title = "Simple constructions for multi-terminal network
		flow synthesis",
	journal= sicomp ,
	volume = 12 ,
	year = 1983,
	pages = "157--165"	}

@article{kn:GusfieldMartelFenandez87 ,
	author = "Gusfield, Dan  and  Charles Martel  and David
		Fernandez-Baca " ,
	title = "Fast algorithms for bipartite network flow" ,
	journal= sicomp ,
	volume = 16 ,
	year = 1987,
	pages = "237--251"	}

@article{kn:Gusfield90 ,
	author = "Gusfield, Dan" ,
	title = "Very simple methods for all pairs network flow
		analysis" ,
	journal= sicomp ,
	volume = 19 ,
	year = 1990,
	pages = "143--155"	}

@article{kn:Hamachar79 ,
	title = "Numerical investigations on the maximal flow algorithm
		of {K}arzanov" ,
	author = "Hamachar, H." ,
	journal= "Computing" ,
	volume = 22 ,
	year = 1979,
	pages = "17--29"	}

@article{kn:HamacharFoulds89 ,
	title = "Algorithms for flows with parametric capacities" ,
	author = "Hamachar, H.  and  L. R. Foulds" ,
	journal= "Z. Oper. Res." ,
	volume = 33 ,
	year = 1989,
	pages = "21--37"	}

@article {kn:HartmanLasd71 ,
	title = "A generalized upper-bounding algorithm for
		multicommodity network flow problems" ,
	author = "Hartman, J. K.  and  L. S. Lasdon" ,
	journal = "Networks" ,
	volume = 1 ,
	year = 1971 ,
	pages = "333--354"	}

@article{kn:Hassin81 ,
	author = "Refael Hassin" ,
	title = "Maximum flow in $(s,t)$ planar networks",
	journal= ipl ,
	volume = 13 ,
	year = 1981,
	pages = "107--107"	}

@article {kn:Hassin82 ,
	title = "Minimum cost flow in set-constraints" ,
	author = "Refael Hassin" ,
	journal = "Networks" ,
	volume = 12 ,
	year = 1982 ,
	pages = "1--21"	}

@article{kn:Hassin85 ,
	author = "Refael Hassin" ,
	title = "On multicommodity flow in planar graphs",
	journal= "Networks" ,
	volume = 14 ,
	year = 1985,
	pages = "225--235"	}

@article{kn:HassinJohnson85 ,
	author = "Refael Hassin and Donald B. Johnson " ,
	title = "An ${O}(n \log ^{2} n)$ algorithm for maximum flow in
		undirected planar networks" ,
	journal= sicomp ,
	volume = 14 ,
	year = 1985,
	pages = "612--624"	}

@article{kn:HassinZemel88 ,
	title = "Probabilistic analysis of the capacitated
		transportation problem" ,
	author = "Refael Hassin  and  Eitan Zemel" ,
	journal= "Math. Oper. Res." ,
	volume = 13 ,
	year = 1988,
	pages = "80--89"	}

@article{kn:HelgasonKenn77 ,
	title = "An efficient procedure for implementing a dual simplex
		network flow algorithm" ,
	author = "Helgason, R. V.  and  J. L. Kennington" ,
	journal= "A.I.I.E. Trans. " ,
	volume = 9 ,
	year = 1977,
	pages = "63--68"	}

@article{kn:Hitchcock41 ,
	title = "The distribution of a product from several sources to
		numerous facilities" ,
	author = "Hitchcock, F. L." ,
	journal= "J. Math. Phys." ,
	volume = 20 ,
	year = 1941,
	pages = "224--230"	}

@article{kn:HochbSegev89 ,
	title = "Analysis of a flow problem with fixed charges" ,
	author = "Hochbaum, D. S.  and  A. Segev" ,
	journal= "Networks" ,
	volume = 19 ,
	year = 1989,
	pages = "291--312"	}

@article{kn:Hu63 ,
	title = "Multicommodity network flows" ,
	author = "Hu, T. C." ,
	journal= opres ,
	volume = 11 ,
	year = 1963,
	pages = "344--360"	}

@book {kn:Hu69 ,
	title = "Integer Programming \& Network Flows",
	author = "Hu, T. C." ,
	publisher = "Addison-Wesley Publ. Comp." ,
	address = "Reading, Mass." ,
	year = 1969	}

@inbook {kn:Hu82 ,
	title = "Combinatorial Algorithms" ,
	author = "Hu, T. C." ,
	chapter = "2.1, 2.2 and 2.3" ,
	publisher = "Addison-Wesley Publ. Comp." ,
	address = "Reading, Mass." ,
	year = 1982	}

@article{kn:HuShing83 ,
	title = "Multiterminal flows in outerplanar graphs" ,
	author = "Hu, T. C. and Shing, M. T." ,
	journal= jalg ,
	volume = 4 ,
	year = 1983,
	pages = "241--261"	}

@techreport{kn:HuShing84 ,
	title = "A decomposition algorithm for multi-terminal network
		flows" ,
	author = "Hu, T. C.  and  M. T. Shing" ,
	number = "TRCS 84-08" ,
	institution = DCSU # "California" ,
	address = "Santa Barbara, CA" ,
	year = 1984 }

@article{kn:IchimoriIshNis81 ,
	title = "Weighted minimax real-valued flow" ,
	author = "Ichimori, T.  and  H. Ishii  and  T. Nishida" ,
	journal= "J. Oper. Res. Soc. Japan" ,
	volume = 24 ,
	year = 1981,
	pages = "52--59"	}

@article{kn:Imai83 ,
	title = "On the practical efficiency of various maximum flow
		algorithms" ,
	author = "Imai, H.",
	journal= "J. Oper. Res. Soc. Japan" ,
	volume = 26 ,
	year = 1983,
	pages = "61--82"	}

@article{kn:Iri60 ,
	title = "A new method of solving transportation-network
		problems" ,
	author = "Iri, M." ,
	journal= "J. Oper. Res. Soc. Japan" ,
	volume = 3 ,
	year = 1960,
	pages = "27--87"	}

@book{kn:Iri69 ,
	title = "Network Flows, Transportation and Scheduling" ,
	author = "Iri, M." ,
	publisher = "Academic Press" ,
	address = "New York" ,
	year = 1969	}

@article{kn:Itai78 ,
	title = "Two-commodity flow" ,
	author = "Alon Itai" ,
	journal= jacm ,
	volume = 25 ,
	year = 1978,
	pages = "596--611"	}

@article{kn:ItaiShiloach79 ,
	title = "Maximum flows in planar networks",
	author = "Alon Itai and Y. Shiloach",
	journal= sicomp ,
	volume = 8 ,
	year = 1979,
	pages = "135--150"	}

@article {kn:ItaiPrad84 ,
	title = "Synthesis of directed multicommodity flow networks" ,
	author = "Itai, A.  and  D. K. Pradhan" ,
	journal = "Networks" ,
	volume = 14 ,
	year = 1984 ,
	pages = "213--224"	}

@article{kn:JanigaKoubek85 ,
	author = "Janiga, L.  and  V. Koubek" ,
	title = "A note on finding cuts in directed planar networks by
		parallel computation" ,
	journal= ipl ,
	volume = 21 ,
	year = 1985,
	pages = "75--78"	}

@article{kn:Jarvis69 ,
	title = "On the equivalence between node-arc and arc-chain
		formulations for the multicommodity maximal flow
		problem" ,
	author = "Jarvis, J. J." ,
	journal= "Naval Res. Log. Quart." ,
	volume = 16 ,
	year = 1969,
	pages = "525--529"	}

@article{kn:JarvisJez72 ,
	title = "Maximal flow with gains through a special network" ,
	author = "Jarvis, J. J.  and  A. M. Jezior" ,
	journal= opres ,
	volume = 20 ,
	year = 1972,
	pages = "678--688"	}

@book{kn:JensenBarn80 ,
	title = "Network Flow Programming" ,
	author = "Jensen, P. A.  and  W. Barnes" ,
	publisher = "J. Wiley \& Sons" ,
	address = "New York" ,
	year = 1980	}

@article{kn:JensenBhaum77 ,
	title = "A flow augmentation approach to the network with gains
		minimum cost flow problem" ,
	author = "Jensen, P. A.  and  G. Bhaumik" ,
	journal= "Manag. Sci." ,
	volume = 23 ,
	year = 1977,
	pages = "631--643"	}

@booklet{kn:Jewell58 ,
	title = "Optimal flow through networks" ,
	author = "Jewell, W. S." ,
	howpublished = "Interim Technical Report No. 8" ,
	address = "Operations Research Center, MIT, Cambridge, Mass." ,
	year = 1958 }

@article{kn:Jewell62 ,
	title = "Optimal flow through networks with gains" ,
	author = "Jewell, W. S." ,
	journal= opres ,
	volume = 10 ,
	year = 1962,
	pages = "476--499"	}

@misc{kn:Jewell66 ,
	title = "A primal-dual multicommodity flow algorithm" ,
	author = "Jewell, W. S." ,
	howpublished = "ORC Report 66-24, Operations Research Center,
		University of California, Berkeley, CA" ,
	year = 1966	}

@misc{kn:Jewell67 ,
	title = "Multicommodity network solutions" ,
	author = "Jewell, W. S." ,
	howpublished = "In {\em Th\'{e}orie des graphes}. Dunod, Paris,
		page 183" ,
	year = 1967	}

@article{kn:Johnson66 ,
	title = "Networks and basis solutions" ,
	author = "Johnson, E. L.",
	journal= opres ,
	volume = 14 ,
	year = 1966,
	pages = "619--624"	}

@inproceedings {kn:JohnsonVenk82 ,
	title = "Using divide and conquer to find flows in directed
		planar networks in ${O}(n^{3/2} \log n)$ time" ,
	author = "Johnson, D. B.  and  S. Venkatesan" ,
	booktitle = "Proc. 20th Annual Allerton Conf. on Communication,
		Control, and Computing" ,
	address  = "Univ. of Illinois, Urbana-Champaign, IL." ,
	pages = "898--905" ,
	year = 1982	}

@article{kn:Johnson87 ,
	title = "Parallel algorithms for minimum cuts and maximum
		flows in planar networks",
	author = "Johnson, D. B.",
	journal= jacm ,
	volume = 34 ,
	year = 1987,
	pages = "950--967",
	note = "Prelimanary version in Proc. 23rd " # focs # ", pages
		244--254, 1982"	}

@article{kn:KapoorVaidya ,
	title = "Speeding up {K}armarkar's algorithm for multicommodity
		flows" ,
	author = "Kapoor, S.  and  Pravin M. Vaidya" ,
	journal= "Math. Progr." ,
	note = "To appear."	}

@inproceedings {kn:KapoorVaidya86 ,
	title = "Fast algorithms for convex quadratic programming and
		multicommodity flows" ,
	author = "Sanjiv Kapoor  and  Pravin M. Vaidya" ,
	booktitle = "Proc. 18th " # stoc ,
	year = 1986 ,
	pages = "147--159"	}

@article{kn:Karp78 ,
	title = "A characterization of the minimum cycle mean in a
		digraph" ,
	author = "Karp, Richard M" ,
	journal= "Discrete Math." ,
	volume = 23 ,
	year = 1978 ,
	pages = "309--311"	}

@article{kn:KarpUpfalWigd86 ,
	title = "Constructing a maximum matching is in {R}andom {NC}" ,
	author = "Karp, Richard M  and  Eli Upfal  and  A Wigderson" ,
	journal= "Combinatorica" ,
	volume = 6 ,
	year = 1986 ,
	pages = "35--48"	}

@article{kn:Karzanov74 ,
	title = "Determining the maximal flow in a network by the
		method of preflows" ,
	author = "Karzanov, A. V." ,
	journal= "Soviet Math. Dokl." ,
	volume = 15 ,
	year = 1974 ,
	pages = "434--437"	}

@article{kn:KenningtonShal77 ,
	title = "An effective subgradient procedure for minimal cost
		multicommodity flow problems" ,
	author = "Kennington, J. L.  and  M. Shalaby" ,
	journal= "Manag. Sci." ,
	volume = 23 ,
	year = 1977,
	pages = "994--1004"	}

@article{kn:Kennington78 ,
	title = "Survey of linear cost multicommodity network flows" ,
	author = "Kennington, J. L." ,
	journal= opres ,
	volume = 26 ,
	year = 1978,
	pages = "209--236"	}

@book {kn:KenningtonHelg80 ,
	title = "Algorithms for Network Programming" ,
	author = "Kennington, J. L.  and  R. V. Helgason" ,
	publisher = "Wiley-Interscience" ,
	address = "New York" ,
	year = 1980	}

@article{kn:KinariwalaRao77 ,
	title = "Flow switching approach to the maximum flow problem" ,
	author = "Kinariwala, A. B.  and  A. G. Rao" ,
	journal= jacm ,
	volume = 24 ,
	year = 1977,
	pages = "630--645"	}

@article{kn:Klein67 ,
	title = "A primal method for minimal cost flows with
		applications to the assignment and transportation
		problems" ,
	author = "Klein, M." ,
	journal= "Manag. Sci." ,
	volume = 14 ,
	year = 1967,
	pages = "205--220"	}

@article{kn:Kleitman71 ,
	title = "An algorithm for certain multicommodity flow
		problems" ,
	author = "Kleitman, Daniel J" ,
	journal= "Networks" ,
	volume = 1 ,
	year = 1971,
	pages = "75--90"	}

@article {kn:Klincew83 ,
	title = "A {N}ewton method for convex separable network flow
		problems" ,
	author = "Klincewicz, J. G." ,
	journal = "Networks" ,
	volume = 13 ,
	year = 1983 ,
	pages = "427--442"	}

@article{kn:KlingmanNapSt74 ,
	title = "N{ETGEN}:  {A} program for generating large scale
		capacitated assignment, transportation, and minimum
		cost flow network problems" ,
	author = "Klingman, D.  and  A. Napier  and  J. Stutz" ,
	journal= "Manag. Sci." ,
	volume = 20 ,
	year = 1974,
	pages = "814--821"	}

@inproceedings{kn:Koopmans47 ,
	title = "Optimum utilization of the transportation system" ,
	author = "Koopmans, T. C." ,
	booktitle = "Proc. International Statistical Conference" ,
	address = "Washington, D.C." ,
	year = 1947,
	note = "Also reprinted as supplement to {\em Econometrica}
		{\bf 17}, 1949"	}

@inproceedings{kn:KoubekRicha81 ,
	title = "The maximum $k$-flow in a network" ,
	author = "Koubek, Vaclav  and  Antonin Riha" ,
	booktitle = "Proc. Mathem. Foundations of Computer Science" ,
	editor = "Gruska, J.  and  M. Chytil" ,
	series =  lncs # "118" ,
	address = "Springer-Verlag, Berlin" ,
	year = 1981,
	pages = "389--397"	}

@inproceedings{kn:Kucera81 ,
	title = "Maximum flow in planar networks" ,
	author = "L. Kucera" ,
	booktitle = "Proc. Mathem. Foundations of Computer Science" ,
	editor = "Gruska, J.  and  M. Chytil" ,
	series = lncs # "118" ,
	address = "Springer-Verlag, Berlin" ,
	year = 1981,
	pages = "418--422" ,
	note = "\\ Implementation of \cite{kn:ItaiShiloach79} with
		linear average running time on special class of planar
		graphs"
	}

@inproceedings{kn:Kucera84 ,
	title = "Finding a maximum flow in /S,T/-planar network in
		linear expected time" ,
	author = "L. Kucera" ,
	booktitle = "Proc. Mathem. Foundations of Computer Science" ,
	editor = "Chytil, M. P. and V. Koubek" ,
	series = lncs # "176" ,
	address = "Springer-Verlag, Berlin" ,
	year = 1984,
	pages = "370--377"	}

@inbook {kn:Lawler76 ,
	title = "Combinatorial Optimization: Networks and Matroids" ,
	author = "Eugene L. Lawler" ,
	chapter = "4, 6.3 and 7.11" ,
	publisher = "Holt, Rinehart and Winston" ,
	address = "New York" ,
	year = 1976	}

@article{kn:Lawler79 ,
	title = "Shortest path and network flow algorithms" ,
	author = "Eugene L. Lawler" ,
	journal= "Ann. Discr. Math." ,
	volume = 4 ,
	year = 1979,
	pages = "251--263"	}

@article{kn:LawlerMartel82 ,
	title = "Computing maximal {"polymatroidal"} network flow" ,
	author = "Eugene L. Lawler  and  C. U. Martel" ,
	journal= "Math. Oper. Res." ,
	volume = 7 ,
	year = 1982,
	pages = "334--347"	}

@inproceedings {kn:LeightonRao88 ,
	title = "An approximate max-flow min-cut theorem for uniform
		multicommodity flow problems with applications to
		approximation algorithms" ,
	author = "Tom Leighton  and Satish Rao" ,
	booktitle = "Proc. 29th " # focs ,
	year = 1988 ,
	pages = "422--431"	}

@article {kn:Lomonosov83 ,
	title = "On the planar integer two-flow problem" ,
	author = "M. V. Lomonosov" ,
	journal = "Combinatorica" ,
	volume = 3 ,
	year = 1983 ,
	pages = "207--218"	}

@article {kn:MalekZavAgg72 ,
	title = "Optimal flow in networks with gains and costs" ,
	author = "Malek-Zavarei, M.  and  J. K. Aggarwal" ,
	journal = "Networks" ,
	volume = 1 ,
	year = 1972 ,
	pages = "355--365"	}

@article {kn:MalekZavFr72 ,
	title = "On the fixed cost flow problem" ,
	author = "Malek-Zavarei, M.  and  I. T. Frisch" ,
	journal = "Int. J. Control" ,
	volume = 16 ,
	year = 1972 ,
	pages = "897--902"	}

@article {kn:MalhotraKumarMahes78 ,
	title = "An ${O}( n^{3} )$ algorithm for finding maximum
		flows in networks",
	author = "Malhotra, V. M.  and  M. Pramodh Kumar  and
		S. N. Maheshwari",
	journal = ipl ,
	volume = 7 ,
	year = 1978 ,
	pages = "277--278"	}

@inproceedings {kn:MarbergGafni87 ,
	title = "An ${O}(n^{2}m^{1/2})$ distributed max-flow
		algorithm" ,
	author = "John M. Marberg  and   Eli Gafni" ,
	booktitle = "Proc. International Conf. on Parallel Processing" ,
	editor = "S. Sahni" ,
	year = 1987 ,
	pages = "213--216"	}

@article {kn:Martel89 ,
	title = "A comparison of phase and non-phase network flow
		algorithms" ,
	author = "Martel, C." ,
	journal = "Networks" ,
	volume = 19 ,
	year = 1989 ,
	pages = "691--705"	}

@article{kn:MatsumotoNishSaito85 ,
	author = "Kazuhiko Matsumoto  and  Takao Nishizeki  and
		Nobuji Saito" ,
	title = "An efficient algorithm for finding multicommodity
		flows in planar networks" ,
	journal= sicomp ,
	volume = 14 ,
	year = 1985,
	pages = "289--302"	}

@article{kn:MatsumotoNishSaito86 ,
	author = "Kazuhiko Matsumoto  and  Takao Nishizeki  and
		Nobuji Saito" ,
	title = "Planar multicommodity flows, maximum matchings and
		negative cycles" ,
	journal= sicomp ,
	volume = 15 ,
	year = 1986,
	pages = "495--510"	}

@article{kn:Maurras72 ,
	author = "Maurras, J. F." ,
	title = "Optimization of the flow through networks with gains" ,
	journal= "Math. Progr." ,
	volume = 3 ,
	year = 1972,
	pages = "135--144"	}

@article{kn:Megiddo74 ,
	author = "Megiddo, Nimrod" ,
	title = "Optimal flows in networks with multiple sources and
		sinks" ,
	journal= "Math. Progr." ,
	volume = 7 ,
	year = 1974,
	pages = "97--107"	}

@article{kn:Megiddo77 ,
	author = "Megiddo, Nimrod" ,
	title = "A good algorithm for lexicographically optimal
		flows in multi-terminal terminals" ,
	journal= "Bull. of the AMS" ,
	volume = 83 ,
	year = 1977,
	pages = "97--107"	}

@inbook {kn:Mehlhorn84 ,
	title = "Data structures and Algorithms; vol. 2, Graph
		Algorithms and NP-completeness",
	author = "Kurt Mehlhorn" ,
	chapter = "IV.9" ,
	publisher = "Springer-Verlag" ,
	address = "Berlin" ,
	year = 1984	}

@inproceedings {kn:MillerNaor89 ,
	title = "Flow in planar graphs with multiple sources and sinks,
		 extended abstract" ,
	author = "Miller, Gary L.  and  Joseph Naor" ,
	booktitle = "Proc. 30th " # focs ,
	year = 1989 ,
	pages = "112--117"	}

@article{kn:Minieka72 ,
	author = "Minieka, E." ,
	title = "Optimal flow in a network with gains" ,
	journal= "INFOR" ,
	volume = 10 ,
	year = 1972,
	pages = "171--178"	}

@book {kn:Minieka78 ,
	title = "Optimization Algorithms for Networks and Graphs" ,
	author = "Minieka, E." ,
	publisher = "Marcel Dekker" ,
	address = "New York" ,
	year = 1978	}

@article{kn:Minoux75 ,
	title = "R\'{e}solution des probl\`{e}mes de multiflots en
		nombres entier dans les grands r\'{e}saux" ,
	author = "Minoux, M." ,
	journal = "RAIRO" ,
	volume = 3 ,
	year = 1975 ,
	pages = "21--40"	}

@article{kn:Minoux76a ,
	title = "Multiflots de co\^{u}t minimal avec fonctions de
		co\^{u}t concaves" ,
	author = "Minoux, M." ,
	journal = "Annls T\'{e}l\'{e}commun." ,
	volume = 31 ,
	year = 1976 ,
	pages = "77--92"	}

@article{kn:Minoux76b ,
	title = "Flots \'{e}quilibr\'{e}s et flots avec
		s\'{e}curit\'{e}" ,
	author = "Minoux, M." ,
	journal = "E.D.F.-Bull. Direction Etudes et Recherches,
	s\'{e}rie C -- Math\'{e}m., Inform." ,
	volume = 1 ,
	year = 1976 ,
	pages = "5--16"	}

@article{kn:Minoux84 ,
	title = "A polynomial algorithm for minimum quadratic cost flow
		problems" ,
	author = "Minoux, M." ,
	journal = "Europ. J. Oper. Res." ,
	volume = 18 ,
	year = 1984 ,
	pages = "377--387"	}

@article{kn:Minoux89 ,
	title = "Network synthesis and optimum network design problems:
		{M}odels, solution methods and applications" ,
	author = "Minoux, M." ,
	journal = "Networks" ,
	volume = 19 ,
	year = 1989 ,
	pages = "313--360"	}

@article{kn:Minty60 ,
	author = "Minty, G J" ,
	title = "Monotone networks" ,
	journal= "Proc. Royal Soc. London" ,
	volume = "A(257)" ,
	year = 1960,
	pages = "194--212"	}

@article{kn:Mitchell90 ,
	author = "Joseph S. B. Mitchell" ,
	title = "On maximum flows in polyhedral domains" ,
	journal= jcss ,
	volume = 40 ,
	year = 1990,
	pages = "88--123"	}

@article{kn:Mulvey78 ,
	author = "Mulvey, J." ,
	title = "Pivot strategies for primal-simplex network codes" ,
	journal= jacm ,
	volume = 25 ,
	year = 1978,
	pages = "266--270"	}

@book{kn:Murty76 ,
	title = "Linear and Combinatorial Programming" ,
	author = "Murty, K. G." ,
	publisher = "J. Wiley \& Sons" ,
	address = "New York" ,
	year = 1976	}

@article{kn:NagamochiIbaraki89 ,
	author = "Hiroshi Nagamochi  and  Toshihide Ibaraki" ,
	title = "On max-flow min-cut and integral flow properties for
		multicommodity flows in directed networks" ,
	journal= ipl ,
	volume = 31 ,
	year = 1989,
	pages = "279--285"	}

@article{kn:Nakayama87 ,
	title = "A polynomial-time dual simplex algorithm for the
		minimum cost flow problem" ,
	author = "Nakayama, Akira" ,
	journal= "J. Oper. Res. Soc. Japan" ,
	volume = 30 ,
	year = 1987,
	pages = "265--289"	}

@article{kn:Nakayama86 ,
	title = "A polynomial algorithm for the maximum balanced flow
		problem with a constant balancing rate function" ,
	author = "Nakayama, Akira" ,
	journal= "J. Oper. Res. Soc. Japan" ,
	volume = 29 ,
	year = 1986 ,
	pages = "400--410"	}

@inbook {kn:NishizekiChiba88 ,
	title = "Planar Graphs:  Theory and Algorithms" ,
	author = "Nishizeki, Takao  and  N. Chiba" ,
	chapter = "11" ,
	series = "Annals of Discrete Mathematics, vol. 32" ,
	publisher = "North Holland Publ. Comp." ,
	address = "Amsterdam" ,
	year = 1988 ,
	note = "\\ Contains explanation of multicommodity flows (cf.
		\cite{kn:MatsumotoNishSaito85})"
	}

@article{kn:OkamuraSeymour81 ,
	author = "Haruko Okamura  and  P. D. Seymour" ,
	title = "Multicommodity flows in planar graphs" ,
	journal= "J. Combin. Theory" ,
	volume = "B-31" ,
	year = 1981,
	pages = "75--81"	}

@article{kn:Okamura83 ,
	author = "Haruko Okamura" ,
	title = "Multicommodity flows in graphs" ,
	journal= "Discrete Appl. Math." ,
	volume = 6 ,
	year = 1983,
	pages = "55--62"	}

@article{kn:Onaga66 ,
	title = "Dynamic programming of optimum flows in lossy
		communication nets" ,
	author = "Onaga, K." ,
	journal= "IEEE Trans. Circuit Th." ,
	volume = "CT-13" ,
	year = 1966,
	pages = "282--287"	}

@article{kn:Onaga67 ,
	title = "Optimal flows in general communication networks" ,
	author = "Onaga, K." ,
	journal= "J. Franklin Inst." ,
	volume = 283 ,
	year = 1967,
	pages = "308--327"	}

@article{kn:Orlin83 ,
	title = "Maximum throughput-dynamic networks flows" ,
	author = "Orlin, James B." ,
	journal= "Math. Progr." ,
	volume = 27 ,
	year = 1983,
	pages = "214--231"	}

@article{kn:Orlin84a ,
	title = "Minimum convex cost dynamic network flows" ,
	author = "Orlin, James B." ,
	journal= "Math. Oper. Res." ,
	volume = 9 ,
	year = 1984,
	pages = "190--207"	}

@techreport{kn:Orlin84b ,
	title = "Genuinely polynomial simplex and non-simplex algorithms
		for the minimum cost flow problem" ,
	author = "Orlin, James B." ,
	number = "1615-84" ,
	institution = "Sloan School of Management,  MIT" ,
	address = "Cambridge, Mass." ,
	note = "Also as CWI-OS R8504, Center for Mathematics and
		Computer Science, Amsterdam, 1985." ,
	year = 1984	}

@techreport{kn:OrlinAh87 ,
	title = "New distance-directed algorithms for maximum flow and
		parametric maximum flow problems" ,
	author = "Orlin, James B.  and  Ravindra K. Ahuja" ,
	number = "1908-87" ,
	institution = "Sloan School of Management,  MIT" ,
	address = "Cambridge, Mass." ,
	year = 1987	}

@inproceedings {kn:Orlin88 ,
	title = "A faster strongly polynomial minimum cost flow
		algorithm" ,
	author = "James B. Orlin" ,
	booktitle = "Proc. 20th " # stoc ,
	year = 1988 ,
	pages = "377--387"	}

@techreport{kn:OrlinAh88 ,
	title = "New scaling algorithms for assignment and minimum
		cycle mean problems" ,
	author = "Orlin, James B.  and  Ravindra K. Ahuja" ,
	number = "2019-88" ,
	institution = "Sloan School of Management,  MIT" ,
	address = "Cambridge, Mass." ,
	year = 1988	}

@inbook {kn:PapadSteiglitz82 ,
	title = "Combinatorial Optimization, Algorithms and
		Complexity." ,
	author = "Papadimitriou, Christos H.  and Kenneth Steiglitz" ,
	chapter = "4.3, 5.6, 6, 7, 9 and 10.3" ,
	publisher = "Prentice-Hall" ,
	address = "Englewood Cliffs, NJ" ,
	year = 1982	}

@inproceedings {kn:PlotkinTardos90 ,
	title = "Improved dual network simplex" ,
	author = "Serge A. Plotkin  and  {\'{E}} Tardos" ,
	booktitle = "Proc.1st Annual ACM-SIAM Symp. Discrete Algorithms" ,
	year = 1990 ,
	pages = "367--376"	}

@article{kn:Ponstein72 ,
	author = "Ponstein, J." ,
	title = "On the maximal flow problem with real arc capacities" ,
	journal= "Math. Progr." ,
	volume = 3 ,
	year = 1972 ,
	pages = "254--256"	}

@book{kn:PottsOliver72 ,
	title = "Flows in Transportation Networks" ,
	author = "Potts, R. B.  and R. M. Oliver" ,
	publisher = "Academic Press" ,
	address = "New York" ,
	year = 1972	}

@article{kn:Pulat89 ,
	title = "A decomposition algorithm to determine the maximum
		flow in a generalized network" ,
	author = "Pulat, P. Simin" ,
	journal= "Comput. Oper. Res." ,
	volume = 16 ,
	year = 1989 ,
	pages = "161--172"	}

@article{kn:Queyranne80 ,
	title = {Theoretical efficiency of the algorithm "capacity" for
		the maximum flow problem} ,
	author = "Queyranne, M." ,
	journal= "Math. Oper. Res." ,
	volume = 5 ,
	year = 1980 ,
	pages = "258--266"	}

@article{kn:Ramach87 ,
	title = "The complexity of minimum cut and maximum flow
		problems in an acyclic network" ,
	author = "Ramachandran, Vijaya" ,
	journal = "Networks" ,
	volume = 17 ,
	year = 1987 ,
	pages = "387--392"	}

@article{kn:Ramakrishnan80 ,
	author = "Ramakrishnan, K. G.",
	title = "Solving two-commodity transportation problems
		with coupling constraints",
	journal= jacm ,
	volume = 27 ,
	year = 1980 ,
	pages = "736--757"	}

@article{kn:Reif83 ,
	author = "John H. Reif ",
	title = "Minimum $s$-$t$ cut of a planar undirected network
		in ${O}(n \log ^{2} (n))$ time" ,
	journal= sicomp ,
	volume = 12 ,
	year = 1983,
	pages = "71--81"	}

@inproceedings {kn:Rock80 ,
	title = "Scaling techniques for minimum cost network flows" ,
	author = "R{\"{o}}ck, H." ,
	booktitle = "Discrete Structures and Algorithms" ,
	editor = "U. Pape" ,
	address = "Carl Hansen Verlag, {M\"{u}nchen}" ,
	year = 1980 ,
	pages = "181--191"	}

@book{kn:Rockafellar84 ,
	title = "Network Flows and Monotropic Optimization",
	author = "Rockafellar, R. T." ,
	publisher = "J. Wiley \& Sons" ,
	address = "New York" ,
	year = 1984	}

@article{kn:RothfSheinFr68 ,
	title = "Common terminal multicommodity flow" ,
	author = "Rothfarb, B.  and  N. P. Shein  and  I. T. Frisch" ,
	journal= opres ,
	volume = 16 ,
	year = 1968,
	pages = "202--205"	}

@article{kn:RothfFr69 ,
	title = "On the 3-commodity flow problem" ,
	author = "Rothfarb, B.  and  I. T. Frisch" ,
	journal= "SIAM J. Appl. Math." ,
	volume = 17 ,
	year = 1969,
	pages = "46--58"	}

@article{kn:RothschWhinst66a ,
	title = "On two commodity network flows" ,
	author = "Rothschild, B.  and  A. Whinston" ,
	journal= opres ,
	volume = 14 ,
	year = 1966,
	pages = "377--387"	}

@article{kn:RothschWhinst66b ,
	title = "Feasibility of two commodity network flows" ,
	author = "Rothschild, B.  and  A. Whinston" ,
	journal= opres ,
	volume = 14 ,
	year = 1966,
	pages = "1121--1129"	}

@article{kn:Ruhe88 ,
	title = "Parametric maximal flows in generalized networks --
		Complexity and algorithms" ,
	author = "Ruhe, G." ,
	journal= "Optimization" ,
	volume = 19 ,
	year = 1988,
	pages = "235--251"	}

@techreport{kn:Safer88 ,
	title = "Scaling algorithms for distributed max flow" ,
	author = "Safer, H. M." ,
	institution = "Sloan School of Management, MIT" ,
	address = "Cambridge, Mass." ,
	year = 1988	}

@misc{kn:Saigal68 ,
	title = "Multicommodity flows in directed networks" ,
	author = "Saigal, R." ,
	howpublished = "Operations Research Center,
		University of California, Berkeley, CA" ,
	year = 1968	}

@misc{kn:Sakarovitch66 ,
	title = "The multicommodity maximum flow problem" ,
	author = "Sakarovitch, M." ,
	howpublished = "ORC Report 66-25, Operations Research Center,
		University of California, Berkeley, CA" ,
	year = 1968	}

@article {kn:Sakarovitch73 ,
	title = "Two commodity network flows and linear programming" ,
	author = "Sakarovitch, M." ,
	journal = "Math. Progr." ,
	volume = 4 ,
	year = 1973 ,
	pages = "1--20"	}

@article {kn:SchieberMoran89 ,
	title = "Parallel Algorithms for maximum bipartite matchings
		and maximum 0--1 flows" ,
	author = "Schieber, Baruch  and  Shlomo Moran" ,
	journal = jpdc ,
	volume = 6 ,
	year = 1989 ,
	pages = "20--38"	}

@techreport{kn:Schrijver89a ,
	title = "Applications of polyhedral combinatorics to
		multicommodity flows and compact surfaces" ,
	author = "Schrijver, A." ,
	number = "CWI-BS-R8921" ,
	institution = "Center for Mathematics and Computer Science" ,
	address = "Amsterdam" ,
	year = 1989	}

@techreport{kn:Schrijver89b ,
	title = "Short proofs on multicommodity flows and cuts" ,
	author = "Schrijver, A." ,
	number = "CWI-BS-R8922" ,
	institution = "Center for Mathematics and Computer Science" ,
	address = "Amsterdam" ,
	year = 1989	}

@article {kn:Segall82 ,
	title = "Decentralized maximum-flow protocols" ,
	author = "Adrian Segall" ,
	journal = "Networks" ,
	volume = 12 ,
	year = 1982 ,
	pages = "213--230"	}

@article {kn:SengokuSkinYats88 ,
	title = "On a function for the vulnerability of a directed flow
		network" ,
	author = "Sengoku, Masakazu  and  Shoji Skinoda  and  Reigo
		Yatsuboshi" ,
	journal = "Networks" ,
	volume = 18 ,
	year = 1988 ,
	pages = "73--83"	}

@article {kn:Seymour77 ,
	title = "The matroids with the max-flow min-cut property" ,
	author = "Seymour, P. D." ,
	journal = "J. Comb. Theory" ,
	volume = "B-23" ,
	year = "1977" ,
	pages = "189--222"	}

@article {kn:Seymour78 ,
	title = "A two-commodity cut theorem" ,
	author = "Seymour, P. D." ,
	journal = "Discrete Math." ,
	volume = 23 ,
	year = "1978" ,
	pages = "341--355"	}

@article {kn:Seymour79 ,
	title = "A short proof of the two-commodity flow theorem" ,
	author = "Seymour, P. D." ,
	journal = "J. Comb. Theory" ,
	volume = "B-26" ,
	year = 1979 ,
	pages = "370--371"	}

@article {kn:Seymour80 ,
	title = "Four-terminus flows" ,
	author = "Seymour, P. D." ,
	journal = "Networks" ,
	volume = 10 ,
	year = "1980" ,
	pages = "79--86"	}

@article {kn:Seymour81 ,
	title = "On odd cuts and planar multicommodity flows" ,
	author = "Seymour, P. D." ,
	journal = "Proc. {L}ondon {M}athem. {S}oc." ,
	volume = 42 ,
	year = 1981 ,
	pages = "178--192"	}

@techreport{kn:Shiloach78 ,
	title = "An ${O}(n{I} \log ^{2} {I})$ maximum flow
		algorithm" ,
	author = "Shiloach, Y." ,
	number = "STAN-78-702" ,
	institution = DCS # ", Stanford University" ,
	address = "Stanford, CA" ,
	year = 1978	}

@article {kn:Shiloach79 ,
	title = "Multi-terminal $0-1$ flows" ,
	author = "Shiloach, Y.",
	journal = sicomp ,
	volume = 8 ,
	year = 1979 ,
	pages = "422--430"	}

@article {kn:Shiloach80 ,
	title = "A multi-terminal minimum cut algorithm for planar
		graphs",
	author = "Shiloach, Y.",
	journal = sicomp ,
	volume = 9 ,
	year = 1980 ,
	pages = "214--219"	}

@article {kn:ShiloachVishkin82 ,
	title = "An ${O}(n^{2} \log n)$ parallel max-flow algorithm" ,
	author = "Y. Shiloach  and  Uzi Vishkin" ,
	journal = jalg ,
	volume = 3 ,
	year = 1982 ,
	pages = "128--146"	}

@techreport{kn:ShingAgarw86 ,
	title = "Multi-terminal flows in planar networks" ,
	author = "Shing, M. T.  and  P. K. Agarwal" ,
	number = "TRCS 86-07" ,
	institution = DCSU # "California" ,
	address = "Santa Barbara, CA" ,
	year = 1986 }

@techreport{kn:Sibeyn90 ,
	title = "A pseudo-polylog time parallel maxflow algorithm" ,
	author = "Jop F. Sibeyn" ,
	number = "RUU-CS-90-17" ,
	institution = DCSU # "Utrecht" ,
	address = "Utrecht, The Netherlands" ,
	year = 1990	}

@inproceedings {kn:Simon88 ,
	title = "On minimum flow and transitive reduction" ,
	author = "Simon, Klaus" ,
	booktitle = "Proc. 15th ICALP" ,
	series = lncs # "317",
	address = "Springer-Verlag, Berlin" ,
	year = 1988 ,
	pages = "535--546"	}

@techreport{kn:SleatorTarj80 ,
	title = "An ${O}(nm \log n)$ algorithm for maximum network
		flow" ,
	author = "Sleator, D. D.  and  Robert E. Tarjan" ,
	number = "STAN-CS-80-831" ,
	institution = DCS # ", Stanford University" ,
	address = "Stanford, CA" ,
	year = 1980 }

@article {kn:SleatorTarjan83 ,
	title = "A data structure for dynamic trees" ,
	author = "Sleator, D. D.  and  Robert E. Tarjan" ,
	journal = jcss ,
	volume = 26 ,
	year = 1983 ,
	pages = "362--390"	}

@article {kn:SleatorTarjan85 ,
	title = "Self adjusting binary search trees" ,
	author = "Sleator, D. D.  and  Robert E. Tarjan" ,
	journal = jacm ,
	volume = 32 ,
	year = 1985 ,
	pages = "652--686"	}

@article {kn:SounTruemp80 ,
	title = "Single commodity representation of multicommodity
		networks" ,
	author = "Soun, Y.  and  K. Truemper" ,
	journal = "SIAM J. Discrete Appl. Methods" ,
	volume = 1 ,
	year = 1980 ,
	pages = "348--358"	}

@article {kn:SrinivThomps72 ,
	title = "Accelerated algorithms for labeling and relabeling of
		trees, with applications to distribution problems" ,
	author = "Srinivasan, V.  and  G. L. Thompson" ,
	journal = jacm ,
	volume = 19 ,
	year = 1972 ,
	pages = "712--726"	}

@article {kn:SrinivThomps73 ,
	title = "Benefit-cost analysis of coding techniques for primal
		transportation problems" ,
	author = "Srinivasan, V.  and  G. L. Thompson" ,
	journal = jacm ,
	volume = 20 ,
	year = 1973 ,
	pages = "194--213"	}

@article {kn:SuzukiNishSaito89 ,
	title = "Algorithms for multicommodity flows in planar graphs" ,
	author = "H. Suzuki  and  T. Nishizeki  and  N. Saito" ,
	journal = "Algorithmica" ,
	volume = 4 ,
	year = 1989 ,
	pages = "471--501",
	note = "Preliminary version in Proc. 17th " # stoc # ", pages
		195--204, 1985"	}

@article {kn:Tardos85 ,
	title = "A strongly polynomial minimum cost circulation
		algorithm" ,
	author = "Tardos, {\'{E}}" ,
	journal = "Combinatorica" ,
	volume = 5 ,
	year = 1985 ,
	pages = "247--255"	}

@article{kn:TardosTovTr86 ,
	title = "Layered augmented path algorithms" ,
	author = "Tardos, {\'{E}}  and  C. Tovey  and  M. Trick" ,
	journal= "Math. Oper. Res." ,
	volume = 11 ,
	year = 1986,
	pages = "362--370"	}

@inbook {kn:Tarjan83 ,
	title = "Data Structures and Network Algorithms" ,
	author = "Robert E. Tarjan" ,
	chapter = 8 ,
	publisher = "SIAM" ,
	address = "Philadelphia, PA" ,
	year = 1983	}

@article {kn:Tarjan84 ,
	title = "A simple version of {K}arzanov's blocking flow
		algorithm" ,
	author = "Tarjan, Robert E." ,
	journal = opres # " Lett." ,
	volume = 2 ,
	year = 1984 ,
	pages = "265--268"	}

@article {kn:Tarjan86 ,
	title = "Algorithms for maximum network flow" ,
	author = "Tarjan, Robert E." ,
	journal = "Math. Prog. Study" ,
	volume = 26 ,
	year = 1986 ,
	pages = "1--11"	}

@techreport{kn:Tarjan88 ,
	title = "Efficiency of the primal network simplex algorithm
		for the minimum-cost circulation problem" ,
	author = "Robert E. Tarjan" ,
	number = "CS-TR-187-88" ,
	institution = DCS # ", Princeton University" ,
	address = "Princeton, NJ" ,
	year = 1988 }

@article {kn:Tomizawa72 ,
	title = "On some techniques useful for solution of
		transportation network problems" ,
	author = "Tomizawa, N." ,
	journal = "Networks" ,
	volume = 1 ,
	year = 1972 ,
	pages = "173--194"	}

@article{kn:Tomlin66 ,
	title = "Minimum-cost multicommodity network flows" ,
	author = "Tomlin, J. A." ,
	journal= opres ,
	volume = 14 ,
	year = 1966,
	pages = "45--51"	}

@article{kn:Trotter77 ,
	title = "On the generality of multi-terminal flow theory" ,
	author = "L. E. {Trotter, Jr.}" ,
	journal= "Ann. Discr. Math." ,
	volume = 1 ,
	year = 1977,
	pages = "517--525"	}
 
@article {kn:Truemper77 ,
	title = "On max flows with gains and pure minimum cost flows" ,
	author = "Truemper, K." ,
	journal = "SIAM J. Appl. Math." ,
	volume = 32 ,
	year = 1977 ,
	pages = "450--456"	}

@article {kn:Truemper78 ,
	title = "Optimal flows in nonlinear gain networks" ,
	author = "Truemper, K." ,
	journal = "Networks" ,
	volume = 8 ,
	year = 1978 ,
	pages = "17--36"	}

@article{kn:Truemper87 ,
	title = "Max-flow min-cut matroids: polynomial testing and
		polynomial algorithms for maximum flow and shortest
		routes" ,
	author = "Truemper, K." ,
	journal= "Math. Oper. Res." ,
	volume = 12 ,
	year = 1987,
	pages = "72--96"	}

@article{kn:Tucker77 ,
	title = "A note on the convergence of the {F}ord-{F}ulkerson
		flow algorithm" ,
	author = "Tucker, A." ,
	journal= "Math. Oper. Res." ,
	volume = 2 ,
	year = 1977,
	pages = "143--144"	}

@inproceedings {kn:Vaidya89 ,
	title = "Speeding-up linear programming using fast matrix
		multiplication, (extended abstract)" ,
	author = "Pravin M. Vaidya" ,
	booktitle = "Proc. 30th " # focs ,
	year = 1989 ,
	pages = "332--337"	}

@incollection{kn:VanLeeuwen90 ,
	title = "Graph algorithms" ,
	author = "van Leeuwen, Jan" ,
	booktitle = "Handbook of Theoretical Computer Science, vol. A:
		Algorithms and Complexity" ,
	editor = "{van Leeuwen}, Jan" ,
	publisher = "North-Holland Publ. Comp." ,
	address = "Amsterdam" ,
	year = 1990,
	note = "To appear"	}

@article {kn:Wallace87 ,
	title = "Investing in arcs in a network to maximize the
		expected max flow" ,
	author = "Wallace, Stein W." ,
	journal = "Networks" ,
	volume = 17 ,
	year = 1987 ,
	pages = "87--103"	}

@article{kn:Weintraub74 ,
	title = "A primal algorithm to solve network flow problems with
		convex costs" ,
	author = "Weintraub, A." ,
	journal= "Manag. Sci." ,
	volume = 21 ,
	year = 1974,
	pages = "87--97"	}

@article {kn:Wollmer72 ,
	title = "Multicommodity networks with resource constraints: the
		generalized multicommodity flow problem" ,
	author = "Wollmer, R. D." ,
	journal = "Networks" ,
	volume = 1 ,
	year = 1972 ,
	pages = "245--263"	}

@inproceedings {kn:Yakovleva59 ,
	title = "A problem on minimum transportation cost" ,
	author = "Yakovleva, M A" ,
	booktitle = "Applications of Mathematics in Economic Research" ,
	editor = "Nemchinov, V S" ,
	address = "Izdat. Social'no-Ekon. Lit., Moscow" ,
	year = 1959 ,
	pages = "390--399"	}

@article {kn:Zadeh72 ,
	title = "Theoretical efficiency of the {E}dmonds-{K}arp
		algorithm for computing maximal flows" ,
	author = "Zadeh, N." ,
	journal = jacm ,
	volume = 19 ,
	year = 1972 ,
	pages = "184--192"	}

@article {kn:Zadeh73a ,
	title = "A bad network problem for the simplex method and
		other minimum cost flow algorithms" ,
	author = "Zadeh, N." ,
	journal = "Math. Progr." ,
	volume = 5 ,
	year = 1973 ,
	pages = "255--266"	}

@article {kn:Zadeh73b ,
	title = "More pathological examples for network flow problems" ,
	author = "Zadeh, N." ,
	journal = "Math. Progr." ,
	volume = 5 ,
	year = 1973 ,
	pages = "217--224"	}

@article{kn:Zangwill681 ,
	title = "Minimum concave cost flows in certain networks" ,
	author = "Zangwill, W. I." ,
	journal= "Manag. Sci." ,
	volume = 14 ,
	year = 1968,
	pages = "429--450"	}