Sparse dual transportation polyhedra: Extreme points and signatures (Q911458)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sparse dual transportation polyhedra: Extreme points and signatures |
scientific article |
Statements
Sparse dual transportation polyhedra: Extreme points and signatures (English)
0 references
1990
0 references
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.
0 references
dual transportation polyhedra
0 references
best upper bound
0 references
number of extreme points
0 references
0 references