Computing monotone disjoint paths on polytopes

DOI10.1007/S10878-008-9151-3MaRDI QIDQ1016050zbMATH OpenOpenAlexFDO

Authors David Avis, Bohdan Kaluzny

Publication date 4 May 2009

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-008-9151-3

zbMATH Keywords

degeneracydisjoint pathsHolt-Kleelinear programmingnetwork flowpolytopesreverse searchsimplex methodvertex enumeration

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• On the Holt-Klee property for oriented matroid programming
• On the length of monotone paths in polyhedra
• Long monotone paths on simple 4-polytopes
• scientific article; zbMATH DE number 4204383
• Disjoint paths in symmetric digraphs

Cites work

• A reverse search algorithm for the neighborhood problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• How good are convex hull algorithms?
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1241836 (Why is no real title available?)
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• scientific article; zbMATH DE number 1538127 (Why is no real title available?)
• Lectures on Polytopes
• Maximal Flow Through a Network
• On the existence of a short admissible pivot sequence for feasibility and linear optimization problems
• On the Monotone Upper Bound Problem
• Pivot rules for linear programming: A survey on recent theoretical developments
• Reverse search for enumeration
• The maximum numbers of faces of a convex polytope
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4

Cited in

(4)

• Maximal nonrevisiting paths in simple polytopes
• Families of polytopal digraphs that do not satisfy the shelling property
• On the Holt-Klee property for oriented matroid programming
• The Polyhedral Geometry of Pivot Rules and Monotone Paths

This page was built for publication: Computing monotone disjoint paths on polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016050)