Composition of graphs and the Hop-constrained Path Problem

F. Bendali, J. Mailfert and X. Tang

International Journal of Mathematics in Operational Research, 2012, vol. 4, issue 3, 225-246

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. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=46685 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijmore:v:4:y:2012:i:3:p:225-246

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().