Graph decomposition and a greedy algorithm for edge-disjoint paths
Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, pp.379-380
SODA '04
01/11/2004
A theorem for graph decomposition and a greedy algorithm was proved for edge-disjoint paths (EDP). In the EDP problem, a directed graph and a set of pairs of vertices are given, and the goal is to connect as many pairs as possible by paths with the constraint that no two paths share an edge. The theorem proves that the greedy algorithm for computing EDP in directed graphs is an O(n 2/3 log 2/3n) approximation algorithm. This bound is also the best known approximation factor for the EDP problem in terms of number of the number of vertices.
- Graph decomposition and a greedy algorithm for edge-disjoint paths
- Kasturi VaradarajanGanesh Venkataraman
- Conference proceeding
- Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, pp.379-380
- Society for Industrial and Applied Mathematics
- SODA '04
- English
- 01/11/2004
- Computer Science
- 9984259488202771
17