2013/01/22 by Longkun Guo, Hong Shen, Guo, Longkun +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1301.5070
12 pages
openalex publication_date 2013/01/22 · arxiv created 2013/04/03 · arxiv updated 2013/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given graph G with positive integral cost and delay on edges, distinct vertices s and t, cost bound C∈ Z+ and delay bound D∈ Z+, the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known NP-hard, even when k=1 \citegarey1979computers. This paper first gives a simple approximation algorithm with factor-(2,2), i.e. the algorithm computes a solution with delay and cost bounded by 2*D and 2*C respectively. Later, a novel improved approximation algorithm with ratio (1+β, max\2, 1+ln\frac1β\) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-(1.369, 2) approximation algorithm by setting 1+ln\frac1β=2 and a factor-(1.567, 1.567) algorithm by setting 1+β=1+ln\frac1β. Besides, by setting β=0, an approximation algorithm with ratio (1, O(ln n)), i.e. an algorithm with only a single factor ratio O(ln n) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint.