On the Circuit Diameter of Dual Transportation Polyhedra
On the Circuit Diameter of Dual Transportation Polyhedra
复制标题
关于双传输多面体的电路直径
DOI：
--
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
R. Hemmecke
中科院分区：
文献类型：
--
作者：
S. Borgwardt;E. Finhold;R. Hemmecke
在本文中，我们介绍了Polyhedra的电路直径，Polyhedra始终由组合直径从上方界定。我们考虑在一般两部分图上定义的双转运多面体。对于完整的$ m {imes} n $二分化图，hirsch bound $（m { - } 1）（n { - } 1）$上的nimerial直径上的$是已知的紧密绑定（Balinski，1984）。对于电路直径，我们显示了所有双运输polyhedra在任意两部分图形上定义的所有双运输polyhedra的绑定$ m {+} n { - } 2 $。
In this paper we introduce the circuit diameter of polyhedra, which is always bounded from above by the combinatorial diameter. We consider dual transportation polyhedra defined on general bipartite graphs. For complete $M{ imes}N$ bipartite graphs the Hirsch bound $(M{-}1)(N{-}1)$ on the combinatorial diameter is a known tight bound (Balinski, 1984). For the circuit diameter we show the much stronger bound $M{+}N{-}2$ for all dual transportation polyhedra defined on arbitrary bipartite graphs with $M{+}N$ nodes.