×

On a class of minimum cost circulation problems via strong spanning trees. (English) Zbl 0780.90036

Summary: We solve a certain class of transportation problem using an extension of the concept of strong spanning trees on bipartite graphs. As an application we obtain an \(O(| E|| V|+| V|^ 2\log| V|)\) solution to a certain class of minimum cost circulation problems.

MSC:

90B10 Deterministic network models in operations research
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite