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, doi: 10.1111/j.1475-3995.2007.00577.x.

Attached Files
Name Description MIMEType Size Downloads

Title Polyhedral studies for minimum-span graph labelling with integer distance constraints
Author(s) Mak, VickyORCID iD for Mak, Vicky orcid.org/0000-0002-9306-5780
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
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
DOI 10.1111/j.1475-3995.2007.00577.x
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

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 2 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 855 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Mon, 29 Sep 2008, 08:53:24 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.