文章基本信息

标题：Finding Minimal Unsolvable Structures for Constructive Generation of Graph 3-Colorability Instances
本地全文：下载
作者：Kazunori Mizuno ; Seiichi Nishihara ; Hitoshi Sasaki 等
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2013
卷号：28
期号：3
页码：279-284
DOI：10.1527/tjsai.28.279
出版社：The Japanese Society for Artificial Intelligence
摘要：We have developed the method for systematically generating very hard graph 3-colorability (3COL) instances to clarify phase transition mechanism of combinatorial search problems. In our method, 3COL instances can be generated by repeatedly embedding minimal unsolvable graphs (MUGs). In this paper, we find larger-scale MUGs, which are necessary for our generation method, using genetic algorithms (GAs). We also experimentally demonstrate that the computational cost to solve our 3COL instances generated by using MUGs found by GAs is of an exponential order of the number of vertices and our instances are extraordinarily harder than randomly generated instances.
关键词：graph coloring ; search ; constraint satisfaction ; phase transition ; genetic algorithm