On the disjoint paths problem |
| |
| Authors: | Thành Nguyen |
| |
| Institution: | Center for Applied Mathematics, Cornell University, 657 Rhodes Hall, NY 14853, USA |
| |
| 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  approximation for the edge-disjoint paths problem in undirected graphs, directed acyclic graphs and directed graphs with edge capacity at least 2. |
| |
| Keywords: | Edge-disjoint paths Approximation algorithm Flow Matching |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
