Sparse dual transportation polyhedra: Extreme points and signatures (Q911458)

For dual transportation polyhedra \(D_{m,n}(c)=\{(u,v)|\) \(u_ i+v_ j\leq c_{ij}\), \(u_ 1=0\}\), where c is a sparse \(m\times n\) matrix, a characterization of the extreme points is given via spanning tree signatures of the associated bipartite graph to c. The characterization is used to derive a best upper bound of the number of extreme points of such a polyhedron.