Solving graph coloring problem based on conflict resolution strategies of social community alliance

被引：0

作者：

Zheng J.-L. ^{[1
]}

Shu H.-P. ^{[1
]}

Xu Y.-P. ^{[1
]}

Qiao S.-J. ^{[2
]}

Wen L.-Y. ^{[1
]}

机构：

[1] Department of Software Engineering, Chengdu University of Information Technology, Chengdu

[2] School of Information Science and Technology, Southwest Jiaotong University, Chengdu

来源：

| 1600年 / Univ. of Electronic Science and Technology of China卷 / 45期

关键词：

Cooperation rules; Emergent computing; Graph coloring; Group cooperation; NP-complete; Social computing;

D O I：

10.3969/j.issn.1001-0548.2016.01.001

中图分类号：

O144 [集合论]; O157 [组合数学（组合学）];

学科分类号：

070104 ;

摘要：

This study proposes a computing model based on group cooperation. The data unit of the input is first modeled as group individual, the cooperation rules between individuals are then designed based on the target of the problem. Finally, the problem's global optimal solution is obtained through the emergence phenomenon of individuals' cooperation process. By applying group cooperation model to solve graph coloring problem which has NP-complete complexity, it shows that the proposed model works better than several heuristic methods. Experimental results illustrate that: 1) if the algorithm's dynamics exhibits the edge of chaos phenomenon, the algorithm can solve the problem in linear or sub linear time complexity; 2) if the algorithm's dynamics is completely random or exhibits strong convergence, the algorithm degenerates into brutal force search. © 2016, Editorial Board of Journal of Electronic Science and Technology of China. All right reserved.

引用

页码：2 / 16

页数：14

共 29 条

[1] Leeuwarden N.H., Shared space: Reconciling people, places, traffic, Built Environment, 34, 2, pp. 161-181, (2008)
[2] Bol L., Cunningham W., The Wiki Way, (2001)
[3] Bringsjord S., Taylor J., P=NP, Machine Ethics, 7, 7, pp. 361-374, (2011)
[4] Khatib F., Dimaio F., Crystal structure of a monomeric retroviral protease solved by protein folding game players, Nature Structural and Molecular Biology, 364, 19, pp. 1175-1177, (2011)
[5] Axelrod R., The Evolution of Cooperation, (1997)
[6] Chris A., The Long Tail: Why the Future of Business is Selling Less of More, (2008)
[7] Nicholas C., Fowler J., Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives, (2009)
[8] James S., The Wisdom of Crowds, Economies, Societies and Nations, (2004)
[9] Robert A., The Evolution of Cooperation, (2006)
[10] Tapscott D., Williams A.D., Wikinomics: How Mass Collaboration Changes Everything, (2006)

← 1 2 3 →