Composition of graphs and the Hop-constrained path problem

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.
Type de document :
Article dans une revue
International Journal of Mathematics in Operational Research, Inderscience, 2012, 4 (3), pp.225-246. 〈10.1504/IJMOR.2012.046685〉
Liste complète des métadonnées

https://hal-univ-tours.archives-ouvertes.fr/hal-01003825
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 17:11:30
Dernière modification le : mercredi 27 juin 2018 - 15:18:01

Identifiants

Citation

Fatiha Bendali, Jean Mailfert, Xin Tang. Composition of graphs and the Hop-constrained path problem. International Journal of Mathematics in Operational Research, Inderscience, 2012, 4 (3), pp.225-246. 〈10.1504/IJMOR.2012.046685〉. 〈hal-01003825〉

Partager

Métriques

Consultations de la notice

148