9
$\begingroup$

(Apologies if this is misplaced or too broad. I'm open to suggestions on how to reformulate it.)

I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete optimization algorithms in general. Ford-Fulkerson is my straw-man of a starting point. What were the significant advances prior to that? How far back can we go while still being able to make a reasonable argument that somebody was working on max-flow? How about graph algorithms? How about discrete optimization in general?

I'd also be happy to get references to places where this is discussed.

$\endgroup$
14
$\begingroup$

Usually, Schrijver provides a good source for history. You can look at the following books and an article.

  • Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003.
  • Alexander Schrijver. Theory of Linear and Integer Programming. Wiley 1998.
  • Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 2002, 437-445. http://dx.doi.org/10.1007/s101070100259
  • Alexander Schrijver. On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization, Elsevier, 2005. http://homepages.cwi.nl/~lex/files/histco.pdf
$\endgroup$
3
  • 1
    $\begingroup$ +1 for Schrijver. I added a fourth recommended source, which points to early papers by Frobenius [1912] and Kőnig [1915] on bipartite matching, Boruvka [1926] on minimum spanning trees, Menger [1927] on his so-called "$n$-arc theorem" and again [1930] on the traveing salesman problem, and Tolstoi [1930] on the transportation problem. $\endgroup$ – Jeffε Dec 12 '11 at 10:54
  • $\begingroup$ @JɛffE: Thank you very much for the addition. $\endgroup$ – Yoshio Okamoto Dec 12 '11 at 12:28
  • $\begingroup$ Thank you. The last one, on the history of combinatorial optimization, is exactly what I was looking for. $\endgroup$ – dan_x Dec 12 '11 at 15:43
7
$\begingroup$

Most people cite Euler's 1741 "Bridges of Königsburg" paper as the oldest graph algorithm. Unfortuantely, Euler doesn't actually describe his algorithm in detail, but only gives a half-hearted example:

“When it has been determined that such a journey can be made, one still has to find how it should be arranged. For this I use the following rule: let those pairs of bridges which lead from one area to another be mentally removed, thereby considerably reducing the number of bridges; it is then an easy task to construct the required route across the remaining bridges. and the bridges which have been removed will not significantly alter the route found, as will become clear after a little thought. I do not therefore think it worthwhile to give any further details concerning the finding of the routes.

The first complete proof that all even connected graphs have Eulerian tours is apparently due to Heirholzer more than a century later.

  • Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8:128–140, 1741. Presented to the St. Petersburg Academy on August 26, 1735. Reprinted in Opera Omnia 1(7):1–10.

  • Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6:30–32, 1873.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.