%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 }