|
Size: 1563
Comment: Graph Colouring added
|
← Revision 6 as of 2012-11-20 22:24:10 ⇥
Size: 1819
Comment: Link to sample instances added
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
<<TableOfContents>> |
|
| Line 7: | Line 5: |
| 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. | 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. |
| Line 29: | Line 30: |
| 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).}}} | Given the following 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 31: | Line 38: |
| Output: {{{chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).}}} | Resulting in the output: {{{ chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue). }}} |
| Line 33: | Line 43: |
| == Comment == | Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/graph_colouring-sample.zip|download]] |
| Line 35: | Line 45: |
| This problem was part of the Second and Third ASP Competition and was proposed by Martin Brain. | == Problem Peculiarities == '''Type''': Search '''Competition''': System Track '''Complexity''': NP-complete == Notes and updates == Instances taken from the 2009 competition (60 instances). |
| Line 39: | Line 57: |
| * Affiliation: Vienna University of Technology, Austria | * Affiliation: DBAI, Vienna University of Technology, Austria |
Graph Colouring
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)
Given the following 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).
Resulting in the output:
chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).
Additional sample instances: download
Problem Peculiarities
Type: Search Competition: System Track Complexity: NP-complete
Notes and updates
Instances taken from the 2009 competition (60 instances).
Author(s)
- Author: Johannes Wallner
- Affiliation: DBAI, Vienna University of Technology, Austria
- Original Authors: Yuliya Lierler, Marcello Balduccini
- Affiliation: University of Kentucky and Kodak Research Labs