Hyper Dictionary

English Dictionary Computer Dictionary Video Dictionary Thesaurus Dream Dictionary Medical Dictionary


Search Dictionary:  

Meaning of GRAPH COLOURING

 
Computing Dictionary
 
 Definition: 

A constraint-satisfaction problem often used as a test case in research, which also turns out to be equivalent to certain real-world problems (e.g. register allocation). Given a connected graph and a fixed number of colours, the problem is to assign a colour to each node, subject to the constraint that any two connected nodes cannot be assigned the same colour. This is an example of an np-complete problem.

See also four colour map theorem.

 

 

COPYRIGHT © 2000-2013 HYPERDICTIONARY.COM HOME | ABOUT HYPERDICTIONARY