Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871311 | Discrete Applied Mathematics | 2018 | 17 Pages |
Abstract
This paper has three contributions: First, we compare the hierarchy of diameters for the mÃn-transportation polytopes. We show that the Hirsch conjecture bound of m+nâ1 is actually valid in most of these diameter notions. Second, we prove that for 3Ãn-transportation polytopes the Hirsch conjecture holds in the classical graph diameter. Third, we show for 2Ãn-transportation polytopes that the stronger monotone Hirsch conjecture holds and improve earlier bounds on the graph diameter.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S. Borgwardt, J.A. De Loera, E. Finhold, J. Miller,