J. Sethuraman, A. Mahanti, and D. Saha (India)
ADM, Grouppath, A*, H-I, H-II, WDM rings
In WDM rings, determining minimum number of ADMs is NP-Hard. The best known algorithm namely, Breadth first least interference (BFLI) heuristic gives optimal results in only 77% cases. In this paper, we analyze the problem and suggest a new set covering formulation for minimizing the number of ADMs in WDM rings and use best first search algorithm (A*) with the help of a two heuristics namely H-I and H-II to solve it . Heuristic H-I is an admissible heuristic and can always ensure optimal result where as H-II is an inadmissible heuristic which gives optimal results in most of the cases. We establish through experiments that the search algorithm with the proposed heuristic functions (H-I & H-II) performs better than BFLI.
Important Links:
Go Back
