We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture.
- Authors
Kim, Edward
- Abstract
We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete approach for disproving the Linear Hirsch Conjecture.
- Subjects
GRAPH theory; LOGICAL prediction; POLYHEDRA; CONVEX polytopes; LINEAR programming; COMBINATORICS
- Publication
Mathematical Programming, 2014, Vol 143, Issue 1/2, p357
- ISSN
0025-5610
- Publication type
Article
- DOI
10.1007/s10107-012-0611-2