Finding paths with minimum shared edges

DOI10.1007/s10878-012-9462-2zbMath1282.90219OpenAlexW2104070086WikidataQ62037431 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 algorithmheuristic algorithmsinapproximabilityminimum shared edges problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

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

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