Graph decomposition and a greedy algorithm for edge-disjoint paths
Kasturi Varadarajan, Ganesh Venkataraman · 2004
Abstract Given a directed graph G = (V, E) with n vertices and a parameter l> = 1, we present an algorithm that finds a cut (set of edges) of size O((n2/l2)log2(n/l)) whose removal separates every pair of vertices (s,t) in G such that the minimum distance between s and t in G is at least l. This theorem implies a nearly tight analysis of the greedy algorithm for finding edge-disjoint paths in directed graphs, and gives the best known approximation factor for this problem in terms of the number of vertices.