An O(n) bound for the diameter of transshipment polytopes

An O(n) bound for the diameter of transshipment polytopes

0.00 Avg rating—0 Votes
Article ID: iaor19931116
Country: Netherlands
Volume: 12
Issue: 5
Start Page Number: 297
End Page Number: 299
Publication Date: Nov 1992
Journal: Operations Research Letters
Authors:
Keywords: graphs
Abstract:

The diameter of any transshipment polytope associated to the complete directed graph on n nodes is shown to be less than 2(n-1). This bound is twice the bound given by the Hirsch conjecture and improves the best known bound which is O(n3).

Reviews

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