Polyhedral studies for minimum-span graph labelling with integer distance constraints

Polyhedral studies for minimum-span graph labelling with integer distance constraints

0.00 Avg rating0 Votes
Article ID: iaor2008457
Country: United Kingdom
Volume: 14
Issue: 2
Start Page Number: 105
End Page Number: 121
Publication Date: Mar 2007
Journal: International Transactions in Operational Research
Authors:
Abstract:

This paper studies the polytope of the minimum-span graph labelling problems with integer distance constraints (DC-MSGL). We first introduce a few classes of new valid inequalities for the DC-MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch-and-cut algorithm for solving the DC-MSGL. Following that, we present our polyhedral results on the dimension of the DC-MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC-MSGL on triangular graphs.

Reviews

Required fields are marked *. Your email address will not be published.