Name
Abstract | ||
|---|---|---|
Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph G, two special nodes s and t in G, and a number k, find k paths from s to t in G so as to minimize the number of edges shared among the paths. This is a generalization of the well-known disjoint paths problem. While disjoint paths can be computed efficiently, we show that finding paths with minimum shared edges is NP-hard. Moreover, we show that it is even hard to approximate the minimum number of shared edges within a factor of 2(log1-epsilon) n, for any constant epsilon > 0. On the positive side, we show that there exists a (k - 1)-approximation algorithm for the problem, using an adaption of a network flow algorithm. We design some heuristics to improve the quality of the output, and provide empirical results. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10878-012-9462-2 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Keywords | DocType | Volume |
Minimum shared edges problem,Approximation algorithm,Inapproximability,Heuristic algorithms | Journal | 26 |
Issue | ISSN | Citations |
SP4 | 1382-6905 | 1 |
PageRank | References | Authors |
0.37 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masoud T. Omran | 1 | 18 | 3.08 |
| Jörg-Rüdiger Sack | 2 | 1 | 0.70 |
| Hamid Zarrabi-Zadeh | 3 | 111 | 13.63 |