Facebook pixel tracking

The Science and Information (SAI) Organization publishes open-access peer-reviewed journals in computer science and artificial intelligence.

Contact Info
Email info@thesai.org
Website thesai.org
Follow Us
Contact Info
Email info@thesai.org
Follow Us
Research Article | Open Access |

Maximum-Bandwidth Node-Disjoint Paths

Author 1: Mostafa H Dahshan
International Journal of Advanced Computer Science and Applications (IJACSA) · Vol. 3, No. 3 · Published 2012 · Cited by 16

DOI: https://doi.org/10.14569/IJACSA.2012.030309

Download PDF Cite Call for Papers

Abstract

This paper presents a new method for finding the node-disjoint paths with maximum combined bandwidth in communication networks. This problem is an NP-complete problem which can be optimally solved in exponential time using integer linear programming (ILP). The presented method uses a maximum-cost variant of Dijkstra algorithm and a virtual-node representation to obtain the maximum-bandwidth node-disjoint path. Through several simulations, we compare the performance of our method to a modern heuristic technique and to the ILP solution. We show that, in a polynomial execution time, our proposed method produces results that are almost identical to ILP in a significantly lower execution time.

Keywords

Maximum Bandwidth Disjoint Paths Widest Pair Linear Programming ILP NP-Complete Dijkstra Algorithm Multiple Constrained Path MCP.

How to Cite this Article

Dahshan, M. H. (2012). Maximum-Bandwidth Node-Disjoint Paths. International Journal of Advanced Computer Science and Applications, 3(3). https://doi.org/10.14569/IJACSA.2012.030309

Dahshan, Mostafa H. "Maximum-Bandwidth Node-Disjoint Paths." International Journal of Advanced Computer Science and Applications, vol. 3, no. 3, 2012, https://doi.org/10.14569/IJACSA.2012.030309.

@article{Dahshan2012,
  title     = {Maximum-Bandwidth Node-Disjoint Paths},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {3},
  number    = {3},
  year      = {2012},
  publisher = {The Science and Information Organization},
  author    = {Mostafa H Dahshan},
  doi       = {10.14569/IJACSA.2012.030309},
  url       = {https://doi.org/10.14569/IJACSA.2012.030309}
}

Open Access — licensed under a Creative Commons Attribution 4.0 International License. Unrestricted use, distribution, and reproduction in any medium, even commercially, as long as the original work is properly cited.

Back to Issue
IJACSA Journal Cover

IJACSA