Finding paths with minimum shared edges

Masoud T. Omran (), Jörg-Rüdiger Sack () and Hamid Zarrabi-Zadeh ()
Additional contact information
Masoud T. Omran: Carleton University
Jörg-Rüdiger Sack: Carleton University
Hamid Zarrabi-Zadeh: Sharif University of Technology

Journal of Combinatorial Optimization, 2013, vol. 26, issue 4, No 6, 709-722

Abstract: 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^{\log^{1-\varepsilon}n}$ , for any constant ε>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.

Keywords: Minimum shared edges problem; Approximation algorithm; Inapproximability; Heuristic algorithms (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9462-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:4:d:10.1007_s10878-012-9462-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9462-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().