Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657006 | Journal of Algorithms | 2005 | 19 Pages |
Abstract
Given a simple connected graph G=(V,E) and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F remains simple and has at least two internally disjoint paths between u and v for each pair (u,v)âR. The problem is known to be NP-hard, and a 3/2-approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an O(|E|+|R|) time 4/3-approximation algorithm to the problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hiroshi Nagamochi,