Partitioning based algorithms for some colouring problems
(2006) Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005 3978. p.44-58- Abstract
- We discuss four variants of the graph colouring problem, and present algorithms for solving them. The problems are k-COLOURABILITY, MAX IND k-COL, MAX VAL k-COL, and, finally, MAX k-COL, which is the unweighted case of the MAX k-CUT problem. The algorithms are based on the idea of partitioning the domain of the problems into disjoint subsets, and then considering all possible instances were the variables are restricted to values from these partitions. If a pair of variables have been restricted to different partitions, then the constraint between them is always satisfied since the only allowed constraint is disequality.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/399775
- author
- Angelsmark, Ola LU and Thapper, Johan
- organization
- publishing date
- 2006
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science (Recent Advances in Constraints, Revised Selected and Invited Papers)
- volume
- 3978
- pages
- 44 - 58
- publisher
- Springer
- conference name
- Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005
- conference location
- Uppsala, Sweden
- conference dates
- 2005-06-20 - 2005-06-22
- external identifiers
-
- wos:000238569200004
- scopus:33746660166
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-540-34215-1
- DOI
- 10.1007/11754602_4
- language
- English
- LU publication?
- yes
- id
- 3f7e47b1-b0dc-4bc1-9855-ffc035b3390d (old id 399775)
- date added to LUP
- 2016-04-01 11:37:34
- date last changed
- 2024-01-07 14:25:02
@inproceedings{3f7e47b1-b0dc-4bc1-9855-ffc035b3390d, abstract = {{We discuss four variants of the graph colouring problem, and present algorithms for solving them. The problems are k-COLOURABILITY, MAX IND k-COL, MAX VAL k-COL, and, finally, MAX k-COL, which is the unweighted case of the MAX k-CUT problem. The algorithms are based on the idea of partitioning the domain of the problems into disjoint subsets, and then considering all possible instances were the variables are restricted to values from these partitions. If a pair of variables have been restricted to different partitions, then the constraint between them is always satisfied since the only allowed constraint is disequality.}}, author = {{Angelsmark, Ola and Thapper, Johan}}, booktitle = {{Lecture Notes in Computer Science (Recent Advances in Constraints, Revised Selected and Invited Papers)}}, isbn = {{978-3-540-34215-1}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{44--58}}, publisher = {{Springer}}, title = {{Partitioning based algorithms for some colouring problems}}, url = {{http://dx.doi.org/10.1007/11754602_4}}, doi = {{10.1007/11754602_4}}, volume = {{3978}}, year = {{2006}}, }