LESTER RANDOLPH FORD

 
 

ALGORITHMS


Bellman-Ford Algorithm 

 

Complexity Of Bellman-Ford algorithm

 

Ford -Fulkerson Algorithm

 

PAPERS

       RAND-Corporation Papers

Other Papers

 

COMPUTER CODES

 Ford-Fulkerson Algorithm in C

Ford Fulkerson Algorithm In JAVA

Bellman-Ford Algorithm In C

 

LINKS

SIMULATION

Rand Corporation

 

 



L.R. Ford Jr is one of the pioneers in the field of Network Flow Programming. He is the son of Late L.R. Ford Sr. (who himself is a distinguished mathematician) and was born on 23 SEP 1927. L. R. Ford Sr is also commended with exemplary work in mathematics with works like inventing an absolutely marvelous geometric interpretation of the Farey series. He is also credited with work on Pointwise Discontinuous Functions which in fact was the basis of his work for an M.S. degree from The Department of Mathematics in the University of Missouri-Columbia in 1912. Such was his contribution to mathematics that The Lester R. Ford Award were established in 1964 to recognize authors of articles of expository excellence published in The American Mathematical Monthly or Mathematics Magazine.  He also served as the  editor of the American Mathematical Monthly, 1942-1946, and President of the Mathematical Association of America, 1947-1948. Ford Sr and Ford junior co-authored Automorphic Functions which was published by McGraw-Hill in 1963 and is out of print now.  

Carrying on his fathers footsteps Ford Jr also gave enormous contribution to the field of mathematics His work with D.R. Fulkerson have laid the basis of almost all the research in network flows. The seminal paper of Ford and Fulkerson (1956) on the maximum flow problem established the celebrated maxflow-mincut theorem.

While working with the RAND CORPORATION Ford Jr published numerous papers that not only laid the foundation of network flows but also pawed a way for future research on the topics. His book FLOW IN NETWORKS co-authored with D.R.Fulkerson was published in 1962 by the Princeton University Press. This book contained all his work on networks. A short summery of his work is listed below.  

* Ford and Fulkerson with Elias (1956) solved the maximum flow problem by augmenting path algorithms. 

 * Ford and Fulkerson also showed (1956) that for networks of arbitrary irrational arc capacities the algorithm can perform and infinitive sequence of augmentations and might converge to a value different than the maximum flow.

* Ford and Fulkerson with Elias (1956) solved the maximum flow problem by augmenting path algorithms.   

* Ford in 1956 outlined the first Label correcting algorithm for shortest path problems. It runs in pseudopolynomial time and was improved further by other researchers. Ford and Fulkerson (1962) also studies properties of generic label correcting algorithms. 

 * Ford and Fulkerson also showed (1956) that for networks of arbitrary irrational arc capacities the algorithm can perform and infinitive sequence of augmentations and might converge to a value different than the maximum flow.

* Ford and Fulkerson developed capacitated transportation problem(1957). The book presented thorough discussion of these early contributions. It discusses many transformations of network flow problems.

* Ford and Fulkerson developed the primal dual algorithm for  and then generalized this approach in 1962 to solve minimum cost flow problems.

* Ford and Fulkerson (1958) suggested a column generation approach for solving multicommodity flow problem

* Ford and Fulkerson developed Maximum Dynamic flow Problem in 1958.

* Ford also developed the Tournament Problem with Johnson (1959).

** The book FLOWS IN NETWORS(1962) discuses the feasibility of network flow problems with non-negative lower bounds imposed on arc flow

** The book also contains FLOW DECOMPOSITION THEORY, which is one of the premier methods for solving network flow problems.

Though most of Ford's work was done in association with Fulkerson, the two seemed to have a good association, but he presented a number of papers like the one in 1956 alone. He has been instrumental in giving different algorithm which have been refined over the years and are still used for solving most of network problems.

 

 

This website was made by Nayandeep Singh for the course Network Flow Programming offered by Dr Paul Jensen at the The University of Texas at Austin.

1