Applications of submodular functions
András Frank · Cambridge University Press eBooks · 1993
Submodular functions and related polyhedra play an increasing role in combinatorial optimization. The present survey-type paper is intended to provide a brief account of this theory along with several applications in graph theory. INTRODUCTION In 1960 C.St.J.A. Nash-Williams generalized the following easy but pretty result of H.E. Robbins [1939]: the edges of an undirected graph G can be oriented so that the resulting directed graph D is strongly connected if and only if G is 2-edge-connected. To formulate the generalization let us call a directed graph [undirected graph] κ- edge-connected if there are κ edge-disjoint directed (undirected)) paths from each node to each other.) WEAK ORIENTATION THEOREM 1.1 [Nash-Williams, 1960] The edges of an undirected graph G can be oriented so that the resulting directed graph is κ-edge-connected if and only if G is 2κ-edge-connected. The neccessity of the condition is straightforward and the main difficulty lies in proving its sufficiency. Actually, Nash-Williams proved a stronger result. To formulate it, we need the following notation. Given a directed or undirected graph G, let λ(x, y; G ) denote local edge-connectivity from x to y, that is, the maximum number of edge-disjoint paths from x to y.