Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

• 成果类型: Article
• 署名作者: Kim, Edward D.
• 署名单位: Delft University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0611-2
• 发表日期: 2014
• 页码: 357-370
• 关键词: diameter; polytopes

摘要

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.