Because the concept of a graph was introduced to represent how objects are connected, it is not surprising that connectivity has been a central notion in graph theory since its birth in the 18th century. Various definitions of connectivities have been proposed, for example, edge-connectivity, vertex-connectivity, and their ramifications. Closely related to connectivity are flows and cuts in graphs, where the cut may be regarded as a dual concept of connectivity and flows.

A recent general trend in the research of graph theory appears as a shift to its algorithmic aspects, and improving time and space complexities has been a strong incentive for devising new algorithms. This is also true for topics related to connectivities, flows, and cuts, and much important progress has been made. Such topics include computation, enumeration, and representation of all minimum cuts and small cuts; new algorithms to augment connectivity of a given graph; their generalization to more abstract mathematical systems; and so forth. In view of these, it would be a timely attempt to summarize those results and present them in a unified setting so that they can be systematically understood and can be applied to other related fields.

In these developments, we observe that a simple tool known as maximum adjacency (MA) ordering has been a profound influence on the computational complexity of algorithms for a number of problems. It is defined as follows.