Efficient heuristic algorithms for finding multi-constrained paths
Jingchao Chen · 2003
Quality of service routing, namely, finding multi-constrained paths is a real problem arising in multimedia applications, which has been proven to be NP-complete. The paper presents three polynomial-time scalable algorithms for finding a path subject to two additive constraints: one to be a randomized algorithm and two to be limited path heuristic algorithms. To our best knowledge, so far, the best heuristic algorithm among the existing algorithms is Korkmaz's algorithm. However, from our simulations, our algorithms may achieve not only better performance than Korkmaz's algorithm, but also as good performance as the exact algorithm which searches exhaustively all possible paths in the graph to determine whether there exists a solution or not.