M. Dahshan. International Journal of Advanced Computer Science and Applications(IJACSA), (2012)
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.
%0 Journal Article
%1 IJACSA.2012.030309
%A Dahshan, Mostafa H
%D 2012
%J International Journal of Advanced Computer Science and Applications(IJACSA)
%K Algorithm; Bandwidth; Constrained Dijkstra Disjoint ILP; Linear MCP. Maximum Multiple NP-Complete; Pair; Path; Paths; Programming; Widest
%N 3
%T Maximum-Bandwidth Node-Disjoint Paths
%U http://ijacsa.thesai.org/
%V 3
%X 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.
@article{IJACSA.2012.030309,
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.},
added-at = {2014-02-21T08:00:08.000+0100},
author = {Dahshan, Mostafa H},
biburl = {https://www.bibsonomy.org/bibtex/2e4ff407d5c03aa3c60b76eb9d9f54b4e/thesaiorg},
interhash = {be5c88728e10491cab82446cca798278},
intrahash = {e4ff407d5c03aa3c60b76eb9d9f54b4e},
journal = {International Journal of Advanced Computer Science and Applications(IJACSA)},
keywords = {Algorithm; Bandwidth; Constrained Dijkstra Disjoint ILP; Linear MCP. Maximum Multiple NP-Complete; Pair; Path; Paths; Programming; Widest},
number = 3,
timestamp = {2014-02-21T08:00:08.000+0100},
title = {{Maximum-Bandwidth Node-Disjoint Paths}},
url = {http://ijacsa.thesai.org/},
volume = 3,
year = 2012
}