On the disjoint paths problem

On the disjoint paths problem

0.00 Avg rating0 Votes
Article ID: iaor20073069
Country: Netherlands
Volume: 35
Issue: 1
Start Page Number: 10
End Page Number: 16
Publication Date: Jan 2007
Journal: Operations Research Letters
Authors:
Keywords: graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.