Open AccessEfficient algorithm for Minimum cost flow problem with partial lane reversals
Author(s) -
Urmila Pyakurel
Publication year - 2019
Publication title -
the nepali mathematical sciences report
Language(s) - English
Resource type - Journals
ISSN - 2392-411X
DOI - 10.3126/nmsr.v36i1-2.29970
Subject(s) - minimum cost flow problem , series (stratigraphy) , maximum flow problem , flow (mathematics) , flow network , terminal (telecommunication) , algorithm , arc (geometry) , computer science , time complexity , multi commodity flow problem , out of kilter algorithm , polynomial , mathematical optimization , mathematics , theoretical computer science , geometry , telecommunications , dijkstra's algorithm , graph , shortest path problem , paleontology , mathematical analysis , biology
In this paper, we investigate the minimum cost flow problem in two terminal series parallel network. We present modified minimum cost flow algorithm that computes the maximum dynamic and the earliest arrival flows in strongly polynomial time and also preserves all unused arc capacities. We also present strongly polynomial time minimum cost partial contraflow algorithm that solves both problems with partial reversals of arc capacities on two terminal series parallel networks.