Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Partitioning based algorithms for some colouring problems

Angelsmark, Ola LU and Thapper, Johan (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:
author
and
organization
publishing date
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}},
}