On the Combinatorial Diameters of Parallel and Series Connections

DOI10.1137/22m1490508arXiv2203.09587OpenAlexW4391110088MaRDI QIDQ6188515

No author found.

Publication date: 7 February 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.09587

zbMATH Keywords

oriented matroidparallel connectioncombinatorial diameterHirsch conjecture2-sumseries connection

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Linear programming (90C05) Oriented matroids in discrete geometry (52C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the diameter of lattice polytopes
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• The incidence structure of subspaces with well-scaled frames
• Subspaces with well-scaled frames
• On the diameter of convex polytopes
• Paths on polymatroids
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Improved bounds on the diameter of lattice polytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The Hirsch conjecture is true for (0,1)-polytopes
• The many facets of linear programming
• An asymptotically improved upper bound on the diameter of polyhedra
• On two classes of nearly binary matroids
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• A Forward Simplex Method for Staircase Linear Programs
• Solving staircase linear programs by the simplex method, 1: Inversion
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Oriented Matroids
• Solving staircase linear programs by the simplex method, 2: Pricing
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• On sub-determinants and the diameter of polyhedra

This page was built for publication: On the Combinatorial Diameters of Parallel and Series Connections