Maximal nonrevisiting paths in simple polytopes
type: Item
instance of: scholarly article
title: Maximal nonrevisiting paths in simple polytopes
zbMATH Open document ID: 1027.52006
DOI: 10.1016/S0012-365X(02)00525-3
published in: Discrete Mathematics
publication date: 2003-04-09T00:00:00Z
review text: Let \(\Delta(d,n)\) denote the maximum edge-diameter among all simple \(d\)-dimensional polytopes with \(n\) facets. The Hirsch conjecture states that \(\Delta(d,n)\leq n-d\) for all \(n> d\geq 2\). The nonrevisiting path conjecture states that in any polytope, every pair of vertices is connected by a nonrevisiting path. These two conjectures have been shown to be equivalent. Recently operations on polytopes (such as wedging) have been used to get the best available results related to the Hirsch conjecture. The author uses the same operations to study the maximal number of nonrevisiting paths in simple polytopes.
reviewed by: Charles Leytem
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1895988
zbMATH Keywords: paths
zbMATH Keywords: polytopes
zbMATH Keywords: nonrevisiting conjecture
zbMATH Keywords: Hirsch conjecture
zbMATH Keywords: strong \(d\)-step conjecture
author: Fred B. Holt
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00525-3
OpenAlex ID: W1979257172
Recommended article: Paths on polymatroids
Recommended article: Monotone paths on polytopes
Recommended article: Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
Recommended article: Q3764181
Recommended article: Computing monotone disjoint paths on polytopes
Recommended article: On Shortest Paths in Polyhedral Spaces
Recommended article: On the Length of Monotone Paths in Polyhedra
Recommended article: Simple paths on polyhedra
Recommended article: Q3406747
Recommended article: Lemke Paths on Simple Polytopes
description: scientific article; zbMATH DE number 1895988