Name
Abstract | ||
|---|---|---|
An of an undirected graph is a directed graph obtained by replacing each edge {,} of by exactly one of the arcs (,) or (,). In the , the input is an undirected graph and ordered pairs ( , ), where ∈{1,2,…,}. The goal is to find an orientation of that minimizes the sum over all ∈{1,2,…,} of the distance from to . In the , the input is the same, however the goal is to find for every ∈{1,2,…,} a path between and so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed ≥2, the question of -hardness for the min-sum -paths orientation problem and for the min-sum edge-disjoint paths problem has been open for more than two decades. We study the complexity of these problems when =2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an -hardness proof for the min-sum 2-paths orientation problem yields an -hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time. |
Year | DOI | Venue |
|---|---|---|
2013 | https://doi.org/10.1007/s00224-014-9569-1 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | DocType | Volume |
Graph,Algorithms,Paths,Orientation,Min-sum | Conference | 58 |
Issue | ISSN | Citations |
1 | 1432-4350 | 2 |
PageRank | References | Authors |
0.40 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Trevor I. Fenner | 1 | 135 | 36.89 |
| Oded Lachish | 2 | 204 | 18.19 |
| Alexandru Popa | 3 | 70 | 13.34 |