Deakin home > Deakin University Library > Deakin Research Online > Polyhedral studies for minimum-span graph labelling with integer distance constraints

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

Mak, Vicky 2007, Polyhedral studies for minimum-span graph labelling with integer distance constraints, International transactions in operational research, vol. 14, no. 2, pp. 105-121.


Title Polyhedral studies for minimum-span graph labelling with integer distance constraints
Author(s) Mak, Vicky
Journal name International transactions in operational research
Volume number 14
Issue number 2
Start page 105
End page 121
Publisher Wiley-Blackwell Publishing Ltd
Place of publication Chichester, England
Publication date 2007
ISSN 0969-6016
1475-3995
Keyword(s) graph labelling
polyhedral analysis
integer programming
Summary 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.
Language eng
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2007, International Federation of Operational Research Societies; The Authors
Persistent URL http://hdl.handle.net/10536/DRO/DU:30007550

Document type: Journal Article
Collection: School of Engineering and Information Technology
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in Deakin Research Online is owned by the author, with all rights reserved.

Versions
Version Filter Type
Access Statistics: 349 Abstract Views  -  Detailed Statistics
Created: Mon, 29 Sep 2008, 08:53:24 EST