Finding paths with minimum shared edges

DOI10.1007/S10878-012-9462-2MaRDI QIDQ386426zbMATH OpenOpenAlexDBLPWikidataFDO

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

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 algorithminapproximabilityheuristic algorithmsminimum shared edges problem

Mathematics Subject Classification ID

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

Recommendations

• Finding paths with minimum shared edges
• On finding Min-Min disjoint paths
• scientific article; zbMATH DE number 599010
• Finding the Minimum-Weight k-Path
• scientific article; zbMATH DE number 4202051
• Minimum-link paths revisited
• Connected components and minimum paths
• Finding Minors in Graphs with a Given Path Structure
• Graph path minimization problem
• Finding the shortest paths by node combination

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1487883 (Why is no real title available?)
• A quick method for finding shortest pairs of disjoint paths
• Beyond the flow decomposition barrier
• Finding disjoint paths with different path-costs: Complexity and algorithms
• Finding minimum-cost flows by double scaling
• Improved Approximation Algorithms for Label Cover Problems
• On network design problems: fixed cost flows and the covering steiner problem
• On shortest disjoint paths in planar graphs
• The complexity of finding maximum disjoint paths with length constraints
• The complexity of finding two disjoint paths with min-max objective function

Cited in

(15)

• The parameterized complexity of the minimum shared edges problem
• The minimum vulnerability problem on graphs
• Safety in \(s\)-\(t\) paths, trails and walks
• The parameterized complexity of the minimum shared edges problem
• Finding the Minimum-Weight k-Path
• Approximate separable multichoice optimization over monotone systems
• The minimum vulnerability problem on specific graph classes
• The complexity of routing with collision avoidance
• The minimum vulnerability problem
• The minimum vulnerability problem
• The minimum shared edges problem on grid-like graphs
• Extension complexity, MSO logic, and treewidth
• The unimodular intersection problem
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Finding paths with minimum shared edges

This page was built for publication: Finding paths with minimum shared edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386426)