welcome: please sign in
location: Diff for "GraphColouring"
Differences between revisions 2 and 4 (spanning 2 versions)
⇤ ← Revision 2 as of 2012-11-06 16:35:35 →
Size: 1659
Editor: PatrikSchneider
Comment: Fix
← Revision 4 as of 2012-11-12 15:28:48 → ⇥
Size: 1654
Editor: PatrikSchneider
Comment: Fix
Deletions are marked like this. Additions are marked like this.
Line 2: Line 2:

<<TableOfContents>>
Line 32: 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).}}} 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 34: Line 38:
Output: {{{chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).}}} Output:
{{{
chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).
}}}

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)

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).

Problem Peculiarities

Type: Search Competition: System Track Complexity: NP-complete

Notes and updates

Instances taken from last 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

ASP Competition 2013: GraphColouring (last edited 2012-11-20 22:24:10 by PatrikSchneider)