1994 | OriginalPaper | Buchkapitel
The K-Walk Polyhedron
verfasst von : Collette R. Coullard, A. Bruce Gamble, Jin Liu
Erschienen in: Advances in Optimization and Approximation
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a directed graph G = (V, E), with distinguished nodes s and t, a k-walk from s to t is a walk with exactly k arcs. In this paper we consider polyhedral aspects of the problem of finding a minimum-weight k-walk from s to t. We describe an extended linear programming formulation, in which the number of inequalities and variables is polynomial in the size of G(for fixed k),and all the coefficients have values 0,−1, +1. We apply the projection method on the extended formulation and give two natural linear programming formulations, each having one variable for each arc of G. These correspond to two natural polyhedra: the convex hull of the (s,t)-k-walk incidence vectors, and the dominant of that poly tope. We focus on the dominant. We give three classes of facet constraints, showing that the dominant has an exponential number of facet constraints and that some facet constraints have coefficients as large as the size of V.