A comparative study of networking link enhancement algorithms

Link enhancement provides a better routability and hence survivability of a communication network. Though the problem is NP-complete, good heuristics do exist that can provide near-optimal solutions with negligible computation time. An investigation of different heuristics shows the merit of each approach. It is noted that two major improvements can be made over the linear search algorithms: constrained range (CR) and reduced candidate set (RCS). The search of constrained restricted candidate set (CRCS) has been proven to be the best known heuristic for solving the link enhancement problems: The annealing process or the (r+1)^st chance algorithm can piggy back on a CRCS solution and improves it to the optimal one with negligible incremental computation time