Maximum-Bandwidth Node-Disjoint Paths
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2012, Vol 3, Issue 3
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.
Authors and Affiliations
Mostafa H. Dahshan
Keywords
Related Articles
- EP ID EP114172
- DOI -
- Views 102
- Downloads 0
Embedded System Design and Implementation of an Intelligent Electronic Differential System for Electric Vehicles
This paper presents an experimental study of the electronic differential system with four-wheel, dual-rear in wheel motor independently driven an electric vehicle. It is worth bearing in mind that the electronic differen...
Comparison of Workflow Scheduling Algorithms in Cloud Computing
Cloud computing has gained popularity in recent times. Cloud computing is internet based computing, whereby shared resources, software and information are provided to computers and other devices on demand, like a public...
Development and Role of Electronic Library in Information Technology Teaching in Bulgarian Schools*
The electronic library can be considered as an interactive information space. Its creation substantially supports the communication between the teachers and the student, as well as between the teachers and the parents. T...
English to Creole and Creole to English Rule Based Machine Translation System
Machine translation is the process of translating a text from one language to another, using computer software. A translation system is important to overcome language barriers, and help people communicate between differe...
Identification of Critical Node for the Efficient Performance in Manet
This paper considers a network where nodes are connected randomly and can fail at random times. The critical-node test detects nodes, whose failures are malicious behavior, disconnects or significantly degrades the...