Dynamic Graph Coloring using CCM -- A Model for Emergent Computation
Kanada, Y., SIG Note of Parallel Procesing of Artificial Intelligence, The Society of Artificial Intelligence, SIG-PPAI-9401, pp. 7-12, 1994, Published by JSAI.
[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ Poster postscript file: Part 1, Part 2 ]
[ Poster PDF file : Part 1, Part 2 ]
[ Coloring demo in Java (static coloring) ]
Abstract: Real world computing systems are complex systems that is open to the continually varying environment. Conventional software development methods inherently cannot deal such situations. CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation, which is based on local information. CCM is developed toward establishing a software development methodology based on emergent computation. CCM is a production system with locally computed evaluation functions. A method of coloring vertices of dynamically changing graphs, or a method of radio-wave assignments to moving stations, by using SOOC -- a CCM-based computation language, is explained, and the results of experiments are shown in the present report. Dynamic coloring can be performed using the same production rule and evaluation function as static coloring, and the results can be evaluated using basically the same method and tools.
Introduction to this research theme: CCM: Chemical-Computation Model