Link disjoint paths using auxiliary graph transformation in WDM networks

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


This paper presents a new method for finding two link-disjoint paths in WDM networks under wavelength continuity and lowest cost constraints. Such a problem is considered to be an NP-complete problem, which is only solvable using Integer Linear Programming (ILP). The presented method is based on transforming the original network into an auxiliary network with n × n nodes and 2 mn links, where n is the number of nodes and m is the number of links in the original network, and then applying a modified version of Dijkstra's shortest path algorithm on that network. Despite the larger network size, the execution time of the algorithm is in polynomial order. Considering that the problem is NP-complete, the presented algorithm takes much less time than using ILP, which generally requires exponential time. Yet, it is able to find all available disjoint paths obtainable by ILP.

Original languageEnglish
Pages (from-to)2043-2054
Number of pages12
JournalArabian Journal for Science and Engineering
Issue number8
Publication statusPublished - 01 Jan 2013


Dive into the research topics of 'Link disjoint paths using auxiliary graph transformation in WDM networks'. Together they form a unique fingerprint.

Cite this