Refine
Year of publication
- 2018 (1) (remove)
Document Type
- In Proceedings (1) (remove)
Language
- English (1)
Has Fulltext
- no (1)
Is part of the Bibliography
- no (1)
Institute
We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.