This paper, which was published without an abstract, is concerned with the following problem: A graph G consists of a set V(G) of vertices and a set E(G) of edges each of which is an ordered pair of vertices. These objects, despite their simple structure, can be used to model important properties of a wide variety of mathematical and physical systems. One of their most important applications is to the study of routing in networks. Here, the vertices represent sites (cities, computers, airports) and the edges represent connections (roads, telephones, flights). A fundamental result in routing theory concerns disjoint paths between two specified sets of vertices in a graph G. (A path is a sequence of distinct vertices between each consecutive pair of which there is an edge. The endpoints of a path are the first and last elements of the sequence. The vertices of a path of length at least three form a simple cycle if there is an edge between the path’s endpoints.) Practical polynomial-time algorithms exist to find a maximum cardinality set of vertex disjoint paths between two sets S and T of vertices in a graph. These algorithms can be generalized to solve problems in commodity routing as well as in scheduling and resource allocation. Indeed, practical problems of this type with tens of thousands of nodes are routinely solved.
