go-v.orgdoi

On the Circuit Diameter of Dual Transportation Polyhedra

Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke · SIAM Journal on Discrete Mathematics · 2015

  • DOI 10.1137/140976868
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 2015

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 2015

Abstract

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{\times}N$ bipartite graphs the Hirsch bound (M-1)(N-1) on the combinatorial diameter is a known tight bound [Math. Oper. Res., 9 (1984), pp. 629--633]. 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.

Open the resolved locator · 10.1137/140976868

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 15:32 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/140976868
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.