Greedy algorithms in disordered systems

We discuss search. minimal path and minimal spanning tree algorithms and th eir applications to disordered systems. Greedy algorithms solve these probl ems exactly, and are related to extremal dynamics in physics. Minimal cost path (Dijkstra) and minimal cost spanning tree (Prim) algorithms provide ex tremal dynamics for a polymer in a random medium (the KPZ universality clas s) and invasion percolation (without trapping) respectively. (C) 1994 Elsev ier Science B.V. All rights reserved.