welcome: please sign in
location: Diff for "FinalProblemDescriptions/GraphColouring"
Differences between revisions 3 and 4
⇤ ← Revision 3 as of 2011-01-19 17:01:46 →
Size: 2206
Editor: CarmenSantoro
Comment:
← Revision 4 as of 2011-01-20 14:37:06 → ⇥
Size: 2161
Editor: CarmenSantoro
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
== Predicates ==

 * '''Input''': node/1, link/2, colour/1

 * '''Output''': chosenColour/2
Line 14: Line 8:

== Predicates ==

 * '''Input''': {{{node/1, link/2, colour/1}}}

 * '''Output''': {{{chosenColour/2}}}
Line 21: 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). 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 24: Line 24:

node(1). <<BR>>
node(2). <<BR>>
node(3). <<BR>>
link(1,2). <<BR>>
link(2,1). <<BR>>
link(2,3). <<BR>>
link(3,2). <<BR>>
link(3,1). <<BR>>
link(1,3). <<BR>>
colour(red). <<BR>>
colour(green). <<BR>>
colour(blue). <<BR>>		 {{{
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 41: Line 41:

chosenColour(1,red). <<BR>>
chosenColour(2,green). <<BR>>
chosenColour(3,blue). <<BR>>		 {{{
chosenColour(1,red).
chosenColour(2,green).
chosenColour(3,blue).
}}}
Line 55: Line 55:
{{{
Line 57: Line 57:

== Example ==		 }}}
== Example(s) ==

Graph Colouring

Contents

  1. Graph Colouring
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Calibration
    6. Example(s)
    7. Comment
    8. Author(s)

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

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

Output format

The initial facts and a set of choosenColour predicates, one for each node, specifying the node's colour. Continuing the example: 

chosenColour(1,red). 
chosenColour(2,green). 
chosenColour(3,blue).

Calibration

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

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

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

Example(s)

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

ASP Competition 2011: FinalProblemDescriptions/GraphColouring (last edited 2011-02-02 19:11:33 by MarioAlviano)