Title: Composition of graphs and the Hop-constrained Path Problem

Authors: F. Bendali; J. Mailfert; X. Tang

Addresses: Laboratoire LIMOS-CNRS UMR 6158, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France. ' Laboratoire LIMOS-CNRS UMR 6158, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France. ' Laboratoire LIMOS-CNRS UMR 6158, Complexe Scientifique des Cézeaux, 63177 Aubière Cedex, France

Abstract: Given a graph G = (V,E) and a non negative cost function on edges, the Hop-constrained Path Problem (HPP) consists of finding between two distinguished vertices s and t of V a minimum cost path with no more than L edges where L is a fixed integer. Dahl characterised the dominant of the convex hull of the incidence vectors of st-paths of length bounded by L, denoted by DL(G), for any graph G when L ≤ 3, using trivial, st-cut, and L-path-cut inequalities. A graph G is said L-h-simple if the set of Dahl's inequalities is sufficient to define DL(G). In this paper, we study the L-h-simple property when L ≥ 4. We present some results on the facial structure of the dominant DL(G). We also examine some basic operations on graphs which preserve the L-h-simple property.

Keywords: Hop-constrained paths; dominant; graph composition; polyhedral optimisation; operational research; graphs; routing; telecommunications; communications networks.

DOI: 10.1504/IJMOR.2012.046685

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.225 - 246

Published online: 23 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article