 |
|
|||
| Authors: | Thomas Erlebach, Klaus Jansen |
| Group: | Theory of Communication Networks |
| Type: | Article |
| Title: | The Maximum Edge-Disjoint Paths Problem in Bidirected Trees |
| Year: | 2001 |
| Month: | August |
| Pub-Key: | EJ01sidma |
| Journal: | SIAM Journal on Discrete Mathematics |
| Volume: | 14 |
| Number: | 3 |
| Pages: | 326-355 |
| Abstract: | A bidirected tree is the directed graph obtained from an undirected tree by replacing each undirected edge by two directed edges with opposite directions. Given a set of directed paths in a bidirected tree, the goal of the maximum edge-disjoint paths problem is to select a maximum-cardinality subset of the paths such that the selected paths are edge-disjoint. This problem can be solved optimally in polynomial time for bidirected trees of constant degree, but is APX-hard for bidirected trees of arbitrary degree. For every fixed epsilon>0, a polynomial-time (5/3+epsilon)-approximation algorithm is presented. |
| Resources: | [BibTeX] |
