Name
Abstract | ||
|---|---|---|
We revisit the problem of finding paths with a minimum number of shared edges between two vertices of a graph. An edge is called if it is used in more than one of the paths. We provide a -approximation algorithm for this problem, improving the best previous approximation factor of . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of , where is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to . While the problem is NP-hard, and even hard to approximate to within an factor, we show that the problem is polynomially solvable when is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-35261-4_41 | international symposium on algorithms and computation |
Keywords | DocType | Volume |
Network design,Shared edges,Approximation algorithms,Inapproximability | Journal | 70 |
Issue | ISSN | Citations |
4 | 0178-4617 | 2 |
PageRank | References | Authors |
0.64 | 13 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sepehr Assadi | 1 | 124 | 21.34 |
| Ehsan Emamjomeh-Zadeh | 2 | 27 | 4.90 |
| Ashkan Norouzi-Fard | 3 | 8 | 1.47 |
| Sadra Yazdanbod | 4 | 38 | 6.46 |
| Hamid Zarrabi-Zadeh | 5 | 111 | 13.63 |