Diskretnaya Matematika, Tome 4 (1992) no. 2, pp. 23-31
Citer cet article
M. K. Kravtsov. A proof of the Hirsch conjecture for a class of transportation polytopes. Diskretnaya Matematika, Tome 4 (1992) no. 2, pp. 23-31. http://geodesic.mathdoc.fr/item/DM_1992_4_2_a1/
@article{DM_1992_4_2_a1,
author = {M. K. Kravtsov},
title = {A~proof of the {Hirsch} conjecture for a~class of transportation polytopes},
journal = {Diskretnaya Matematika},
pages = {23--31},
year = {1992},
volume = {4},
number = {2},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_1992_4_2_a1/}
}
TY - JOUR
AU - M. K. Kravtsov
TI - A proof of the Hirsch conjecture for a class of transportation polytopes
JO - Diskretnaya Matematika
PY - 1992
SP - 23
EP - 31
VL - 4
IS - 2
UR - http://geodesic.mathdoc.fr/item/DM_1992_4_2_a1/
LA - ru
ID - DM_1992_4_2_a1
ER -
%0 Journal Article
%A M. K. Kravtsov
%T A proof of the Hirsch conjecture for a class of transportation polytopes
%J Diskretnaya Matematika
%D 1992
%P 23-31
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/DM_1992_4_2_a1/
%G ru
%F DM_1992_4_2_a1
We prove the well-known conjecture on the maximum diameter of a polytope generated by a transportation problem with constraints on the partial sums of the variables. We also establish the Hamiltonian property of the graph of any classical (two-index) transportation polytope.
