A Hypergraph Network Simplex Algorithm
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-64539
- 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.
Verfasserangaben: | Isabel BeckenbachORCiD |
---|---|
Dokumentart: | ZIB-Report |
Datum der Erstveröffentlichung: | 17.07.2017 |
Schriftenreihe (Bandnummer): | ZIB-Report (17-36) |
ISSN: | 1438-0064 |