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 to within a factor of 2log1-</font
>e</font
>n2^{\log^{1-\varepsilon }n}, for any constant ε > 0. On the positive side, we show that there exists a k-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 |
|---|---|---|
2011 | https://doi.org/10.1007/s10878-012-9462-2 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Minimum shared edges problem,Approximation algorithm,Inapproximability,Heuristic algorithms | Graph,Approximation algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Disjoint sets,Existential quantification,Heuristics,Floyd–Warshall algorithm,Multiple edges,Minimum k-cut,Mathematics | Conference |
Volume | Issue | ISSN |
26 | 4 | 1382-6905 |
Citations | PageRank | References |
2 | 0.60 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masoud T. Omran | 1 | 18 | 3.08 |
| Jörg-Rüdiger Sack | 2 | 1099 | 166.07 |
| Hamid Zarrabi-Zadeh | 3 | 111 | 13.63 |