The maximum edge-disjoint paths problem in bidirected trees

DOI10.1137/S0895480199361259MaRDI QIDQ2753529zbMATH OpenFDO

Authors Thomas Erlebach, Klaus Jansen

Publication date 11 November 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199361259

zbMATH Keywords

approximation algorithmsbidirected treesedge-disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
• Edge-disjoint paths revisited
• On the disjoint paths problem
• scientific article; zbMATH DE number 2079393
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Cited in

(12)

• Conversion of coloring algorithms into maximum weight independent set algorithms
• Call control with \(k\) rejections
• Robust online algorithms for dynamic choosing problems
• Parameterized maximum path coloring
• GreedyMAX-type algorithms for the maximum independent set problem
• Competitive algorithms and lower bounds for online randomized call control in cellular networks
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Parameterized maximum path coloring
• Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
• Solving the edge‐disjoint paths problem using a two‐stage method
• The complexity of optimizing atomic congestion
• Minimal multicut and maximal integer multiflow: a survey

This page was built for publication: The maximum edge-disjoint paths problem in bidirected trees

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