Persistency in the assignment and transportation problems

LetG=(U,V,E) be a bipartite graph with weights of its edgesc <Subscript> ij </Subscript>. For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E <Subscript>o</Subscript> is the set of edgesij withx <Subscript> ij </Subscript>=0 for each optimum solution (0-persistent edges);E <Subscript>1</Subscript> is the set of edges withx <Subscript> ij </Subscript> > 0 and constant for each optimum (1-persistent edges) andE <Subscript> w </Subscript> is the set of edges such that there are two optimum solutions x, x′ withx <Subscript> ij </Subscript> ≠x <Subscript> ij </Subscript> <Superscript>1</Superscript> (weakly persistent edges). Copyright Physica-Verlag 1998