Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143223 | Operations Research Letters | 2007 | 7 Pages |
Abstract
Using flow and matching algorithms to solve the problem of finding disjoint paths through a given node, and with a technique of Chekuri and Khanna, we give an O(n) approximation for the edge-disjoint paths problem in undirected graphs, directed acyclic graphs and directed graphs with edge capacity at least 2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Thành Nguyen,