Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems

DOI10.1007/978-3-642-13036-6_16MaRDI QIDQ3569819zbMATH OpenOpenAlexFDO

Authors Andreas Bley, José Neto

Publication date 22 June 2010

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13036-6_16

zbMATH Keywords

approximation algorithmscomplexitygraph algorithmslength-bounded paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Approximation algorithms for disjoint paths and related routing and packing problems
• scientific article; zbMATH DE number 4191702
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• scientific article; zbMATH DE number 1263178
• Approximations for the disjoint paths problem in high-diameter planar networks
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• scientific article; zbMATH DE number 47435

Cited in

(5)

• Trade-offs among degree, diameter, and number of paths
• Length-bounded cuts: proper interval graphs and structural parameters
• On the number of edges in a graph with many two-hop disjoint paths
• Heuristics for finding a maximum number of disjoint bounded paths
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow

This page was built for publication: Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems

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