|
Size: 1772
Comment:
|
← Revision 5 as of 2011-02-02 19:11:33 ⇥
Size: 1491
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| * Input Predicates: node/1, link/2, colour/1 * Output Predicates: chosenColour/2 |
|
| Line 13: | Line 9: |
| == Predicates == | |
| Line 14: | Line 11: |
| == Input == | * '''Input''': {{{node/1, link/2, colour/1}}} * '''Output''': {{{chosenColour/2}}} == Input format == |
| Line 20: | Line 21: |
| A number of link facts which say which nodes are linked. Note that if link(N1,N2). is included then so will link(N2,N1). For example: node(1). node(2). node(3). link(1,2). link(2,1). link(2,3). link(3,2). link(3,1). link(1,3). colour(red). colour(green). colour(blue). |
A number of link facts which say which nodes are linked. Note that if {{{link(N1,N2)}}}. is included then so will {{{link(N2,N1)}}}. |
| Line 40: | Line 25: |
| The initial facts and a set of choosenColour predicates, one for each node, specifying the node's colour. Continuing the example: | A set of choosenColour predicates, one for each node, specifying the node's colour. |
| Line 42: | Line 27: |
| chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue). |
== Example(s) == |
| Line 46: | Line 29: |
| Input: {{{node(1). node(2). node(3). link(1,2). link(2,1). link(2,3). link(3,2). link(3,1). link(1,3). colour(red). colour(green). colour(blue).}}} | |
| Line 47: | Line 31: |
| == Calibration == | Output: {{{chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).}}} |
| Line 49: | Line 33: |
| The Two Possible Values of the Chromatic Number of a Random Graph (with A. Naor) Annals of Mathematics, 162 (3), (2005), 1333-1349. http://www.cs.ucsc.edu/~optas/papers/kcol.pdf |
== Comment == |
| Line 53: | Line 35: |
| Suggests that given a random graph with n nodes and a density of (d/n) then the chromatic number is either k or k+1 where k is the smallest number such that d < 2k log(k). | This problem was part of the Second ASP Competition and was proposed by Martin Brain. |
| Line 55: | Line 37: |
| Thus settings with around 125-150 nodes (135 is good), link density of 0.1 (d = 12-15) and 5 colours gives difficult programs. ./graphGenerator.pl --nodes=$N --density=$D --colours=$C |
== Author(s) == * Author: Yuliya Lierler * Affiliation: University of Kentucky, USA * Author: Marcello Balduccini * Affiliation: Kodak Research Labs, USA |
Graph Colouring
Contents
Problem Description
A graph is a set of nodes and a symmetric, binary link relation on nodes. Given a set of N colours, a graph is colourable if each node can be assigned a colour in such a way that any two nodes that are linked together cannot have the same colour.
Predicates
Input: node/1, link/2, colour/1
Output: chosenColour/2
Input format
A number of node facts which give the names of the nodes. Node names are consecutive, ascending integers starting from 1.
A number of colour facts which give the names of the colours. Colour names start with the sequence "red", "green", "blue".
A number of link facts which say which nodes are linked. Note that if link(N1,N2). is included then so will link(N2,N1).
Output format
A set of choosenColour predicates, one for each node, specifying the node's colour.
Example(s)
Input: node(1). node(2). node(3). link(1,2). link(2,1). link(2,3). link(3,2). link(3,1). link(1,3). colour(red). colour(green). colour(blue).
Output: chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).
Comment
This problem was part of the Second ASP Competition and was proposed by Martin Brain.
Author(s)
- Author: Yuliya Lierler
- Affiliation: University of Kentucky, USA
- Author: Marcello Balduccini
- Affiliation: Kodak Research Labs, USA