An Efficient Approximation Scheme for the Multiple QoS Constraints Routing
Weijun Yang, Yan Yang, Xiaodong Wang, Liang Yang · 2014
It is vital to find a path that satisfies multiple Quality-of-Service (QoS) constraints with the deployment of current emerged services. However, it is not very efficient and effective at finding such a path for existing algorithms. In this paper, an improved version of fully polynomial time approximation scheme (IFPTAS) for multiple constraints path optimal (MCOP) problem was proposed. We find that the presented IFPTAS can find a -approximation path in the network with time complexity (where m is the number of edges and n is the number of nodes) by analyzing the proposed algorithm theoretically, which outperforms the previous best-known algorithm for MCOP.