Computing monotone disjoint paths on polytopes

David Avis () and Bohdan Kaluzny ()
Additional contact information
David Avis: McGill University
Bohdan Kaluzny: McGill University

Journal of Combinatorial Optimization, 2008, vol. 16, issue 4, No 3, 328-343

Abstract: Abstract The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph consisting of the set of vertices and arcs of a polytope P directed by a linear objective function in general position. The study of paths on polytopal digraphs stems from a long standing problem, that of designing a polynomial-time pivot method, or proving none exists. To study disjoint paths it would be useful to have a tool to compute them. Without explicitly computing the digraph we develop an algorithm to compute a maximum cardinality set of source to sink paths in a polytope, even in the presence of degeneracy. The algorithm uses a combination of networks flows, the simplex method, and reverse search. An implementation is available.

Keywords: Polytopes; Linear programming; Reverse search; Vertex enumeration; Disjoint paths; Network flow; Simplex method; Degeneracy; Holt-Klee (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9151-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:16:y:2008:i:4:d:10.1007_s10878-008-9151-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9151-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().