Computing monotone disjoint paths on polytopes |
| |
Authors: | David Avis Bohdan Kaluzny |
| |
Affiliation: | (1) School of Computer, McGill University, Montreal, Canada |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |
|