Finding paths with minimum shared edges

DOI10.1007/s10878-012-9462-2zbMath1282.90219WikidataQ62037431 ScholiaQ62037431MaRDI QIDQ386426

Jörg-Rüdiger Sack, Hamid Zarrabi-Zadeh, Masoud T. Omran

Publication date: 9 December 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9462-2

zbMATH Keywords

approximation algorithm; heuristic algorithms; inapproximability; minimum shared edges problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Parameterized shifted combinatorial optimization, The minimum vulnerability problem on specific graph classes, The minimum vulnerability problem, Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications, The complexity of routing with collision avoidance, The unimodular intersection problem, The parameterized complexity of the minimum shared edges problem, Approximate separable multichoice optimization over monotone systems, The Minimum Vulnerability Problem on Graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On shortest disjoint paths in planar graphs
• The complexity of finding two disjoint paths with min-max objective function
• Finding minimum-cost flows by double scaling
• On network design problems: fixed cost flows and the covering steiner problem
• Beyond the flow decomposition barrier
• A quick method for finding shortest pairs of disjoint paths
• Improved Approximation Algorithms for Label Cover Problems
• Finding disjoint paths with different path-costs: Complexity and algorithms
• The complexity of finding maximum disjoint paths with length constraints