K-pair delay constrained minimum cost routing in undirected networks
Guangting Chen, Guoliang Xue · Symposium on Discrete Algorithms · 2001
We study a problem related to QoS routing in an undirected network where each edge has a delay and a cost. Given a k-pair routing request {(si, ti, di)¦i = l,…,k} where si is ith source node, ti is ith destination node, and di, is the ith delay tolerance, we want to compute a minimum cost network which contains an si-ti path whose delay is at most di for every i. We present an FPTAS for this problem when k is a constant.