Maximum Capacity Path Problem with Arc Reversal
Keywords:
bottleneck path, maxmin path, shortest path, complexityAbstract
In a network with capacitated arcs, the maximum capacity path problem is to find the bottleneck path between two nodes that has the maximum capacity among all the paths between the nodes. In this work, a problem of identification of such a path is considered allowing arc reversals in a directed graph where the capacity of the reversed arc can be added to the capacity of its counterpart. We propose an O(m) algorithm to solve the problem in a directed graph with arcs.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Institute of Science and Technology, T.U.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
The copyright of the articles is held by the Institute of Science and Technology, Tribhuvan University (IoST- TU). The views and interpretations in this journal are those of the author(s). They are not attributable to the IoST-TU and do not imply the expression of any opinion concerning the legal status of any country, territory, city, area of its authorities, or concerning the delimitation of its frontiers or boundaries. The corresponding author is responsible for any conflict of interest between authors and others.
The articles in the Journal of Institute of Science and Technology are licensed under a Creative Commons Attribution- Share Alike 4.0 International License (CC: BY-NC), which permits use, distribution and reproduction in any medium or format, remix, transfer, and build upon the materials for any purpose, even commercially, provided the original work is properly cited.
