Solving Graph Coloring Problem Based on Conflict Resolution Strategies of Social Community Alliance

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.