Lund University Publications
https://lup.lub.lu.se/search
Lund University Lund University Publications2000-01-01T00:00+00:001dailyPartitioning based algorithms for some colouring problems
https://lup.lub.lu.se/search/publication/3f7e47b1-b0dc-4bc1-9855-ffc035b3390d
Angelsmark, OlaThapper, Johan2006We 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.http://lup.lub.lu.se/record/399775http://dx.doi.org/10.1007/11754602_4ISBN: 978-3-540-34215-1wos:000238569200004scopus:33746660166eng3978, pp 44-58 (2006)ISSN: 0302-9743ISSN: 1611-3349Datavetenskap (datalogi)Partitioning based algorithms for some colouring problemscontributiontobookanthology/conferenceinfo:eu-repo/semantics/conferencePapertext