Maximum Capacity Path Problem with Arc Reversal

Authors

DOI:

https://doi.org/10.3126/jist.v27i2.47223

Keywords:

bottleneck path, maxmin path, shortest path, complexity

Abstract

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

Download data is not yet available.
Abstract
57
PDF
97

Downloads

Published

2022-12-31

How to Cite

Nath, H. N. (2022). Maximum Capacity Path Problem with Arc Reversal. Journal of Institute of Science and Technology, 27(2), 77–83. https://doi.org/10.3126/jist.v27i2.47223

Issue

Vol. 27 No. 2 (2022)

Section

Research Articles

License

Copyright (c) 2022 Institute of Science and Technology, T.U.

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

The views and interpretations in this journal are those of the author(s). They are not attributable to the Institute of Science and Technology, T.U. 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 of boundaries.

The copyright of the articles is held by the Institute of Science and Technology, T.U.