Open AccessTransshipment Contraflow on Multi-Terminal Networks
Author(s) -
Urmila Pyakurel
Publication year - 2016
Publication title -
the nepali mathematical sciences report
Language(s) - English
Resource type - Journals
ISSN - 2392-411X
DOI - 10.3126/nmsr.v34i1-2.30015
Subject(s) - transshipment (information security) , reversing , arc (geometry) , time complexity , computer science , terminal (telecommunication) , mathematical optimization , value (mathematics) , computational complexity theory , point (geometry) , dual (grammatical number) , algorithm , mathematics , computer network , geometry , computer security , art , materials science , literature , machine learning , composite material
Contraflow technique is the widely accepted model on network optimization. It allows arc reversal that increases the arc capacities. The earliest arrival transshipment contraflow is an important model that transship the given flow value by sending the maximum amount at each time point from the beginning within given time period by reversing the direction arcs from the sources to the sinks at time zero. This problem has not been solved polynomially on complex networks, i.e., multi-terminal networks yet. However, its 2-value-approximation solution has been found by Pyakurel and Dhamala [13] in pseudopolynomial time complexity. Moreover, they have claimed that for the special case of zero transit time on each arc, the 2-value-approximation solution can be computed in polynomial time complexity. In this paper, we solve their claim presenting an efficient algorithm.