Flows on hypergraphs |
| |
Authors: | Riccardo Cambini Giorgio Gallo Maria Grazia Scutellà |
| |
Affiliation: | (1) Dipartimento di Statistica e Matematica applicata all’Economia, Università di Pisa, Pisa, Italy;(2) Dipartimento di Informatica, Università di Pisa, Pisa, Italy |
| |
Abstract: | We consider the capacitated minimum cost flow problem on directed hypergraphs. We define spanning hypertrees so generalizing the spanning tree of a standard graph, and show that, like in the standard and in the generalized minimum cost flow problems, a correspondence exists between bases and spanning hypertrees. Then, we show that, like for the network simplex algorithms for the standard and for the generalized minimum cost flow problems, most of the computations performed at each pivot operation have direct hypergraph interpretations. |
| |
Keywords: | Flows Leontief flows Hypergraphs Simplex algorithm |
本文献已被 SpringerLink 等数据库收录! |
|