Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints

Longkun Guo, Hong Shen, Kewen Liao

For a given graph $G$ with positive integral cost and delay on edges, distinct vertices $s$ and $t$, cost bound $C\in Z^{+}$ and delay bound $D\in Z^{+}$, the $k$ bi-constraint pat…