TY - CONF
A1 - Beckenbach, Isabel
A2 - Kliewer, Natalia
A2 - Ehmke, Jan Fabian
A2 - BorndĂ¶rfer, Ralf
T1 - A Hypergraph Network Simplex Algorithm
T2 - Operations Research Proceedings 2017
N2 - 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.
Y1 - 2018
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6766
VL - Operations Research Proceedings 2017
SP - 309
EP - 316
PB - Springer
CY - Cham
ER -