File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient bounds on a branch and bound algorithm for graph colouration

TitleEfficient bounds on a branch and bound algorithm for graph colouration
Authors
Issue Date1991
PublisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/0020739X.asp
Citation
International Journal of Mathematical Education in Science and Technology, 1991, v. 22 n. 5, p. 823-832 How to Cite?
AbstractBy a proper colouring of a simple graph, we mean an assignment of colours to its vertices with adjacent vertices receiving different colours. Applications of this graph‐theoretic modelling are numerous, especially in the areas of scheduling and timetabling. We shall refer to a proper colouration that uses a smallest possible number of colours as a minimum (proper) colouration. This number for the graph is simply its chromatic number, the determination of which is well known to be a ‘hard’ problem. In this paper, from the computational point of view of actually constructing a colouration, we examine a simple coalescence/expansion procedure that bases on the branch and bound technique improved by efficient bounding conditions. They include various tightened fathoming criteria as well as complete subgraph determination. For the computer implementation, we also look at the issues of branching rules and the decomposition of solution tree. With these efforts, empirical results show that minimum colourations can be constructed for moderate size graphs, with ‘good’ solutions computed for problems of up to about forty vertices.
Persistent Identifierhttp://hdl.handle.net/10722/75489
ISSN
2015 SCImago Journal Rankings: 0.365

 

DC FieldValueLanguage
dc.contributor.authorChu, SCKen_HK
dc.date.accessioned2010-09-06T07:11:35Z-
dc.date.available2010-09-06T07:11:35Z-
dc.date.issued1991en_HK
dc.identifier.citationInternational Journal of Mathematical Education in Science and Technology, 1991, v. 22 n. 5, p. 823-832en_HK
dc.identifier.issn0020-739Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/75489-
dc.description.abstractBy a proper colouring of a simple graph, we mean an assignment of colours to its vertices with adjacent vertices receiving different colours. Applications of this graph‐theoretic modelling are numerous, especially in the areas of scheduling and timetabling. We shall refer to a proper colouration that uses a smallest possible number of colours as a minimum (proper) colouration. This number for the graph is simply its chromatic number, the determination of which is well known to be a ‘hard’ problem. In this paper, from the computational point of view of actually constructing a colouration, we examine a simple coalescence/expansion procedure that bases on the branch and bound technique improved by efficient bounding conditions. They include various tightened fathoming criteria as well as complete subgraph determination. For the computer implementation, we also look at the issues of branching rules and the decomposition of solution tree. With these efforts, empirical results show that minimum colourations can be constructed for moderate size graphs, with ‘good’ solutions computed for problems of up to about forty vertices.-
dc.languageengen_HK
dc.publisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/0020739X.aspen_HK
dc.relation.ispartofInternational Journal of Mathematical Education in Science and Technologyen_HK
dc.titleEfficient bounds on a branch and bound algorithm for graph colourationen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-739X&volume=22 No5&spage=823&epage=832&date=1991&atitle=Efficient+bounds+on+branch+and+bound+algorithm+for+graph+colourationen_HK
dc.identifier.emailChu, SCK: schu@hku.hken_HK
dc.identifier.authorityChu, SCK=rp00685en_HK
dc.identifier.doi10.1080/0020739910220516-
dc.identifier.hkuros35530en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats