Abstract: Although complete algorithms can be used in finding the optimal solution of a distributed constraint optimization problem， the resource and time consumptions are heavy. On the contrary， the shortcoming can be avoided in incomplete algorithms by obtaining suboptimal solutions. As an effective incomplete algorithm， MULBS can improve the quality of solution and reduce the runtime of solving process. However， there are shortcomings in parallel search and backtracking processes in dealing with conflict assignments. Based on thorough analysis of MULBS， an improved algorithm MULBS⁺ is proposed， which overcomes the disadvantages of backtrack strategy caused by conflict and parallel search strategy in the original algorithm. In MULBS⁺， a minimal conflict selection mechanism is introduced in backtracking. On the other hand， MULBS⁺ adopts global parallel search strategy based on dynamic graph partitioning which can quickly find a better solution in a constraint graph with large density. Experiments show that the proposed algorithm is better than the original one in both execution time and solution quality， except a certain increase of communication information.

Key words: distributed constraint optimization, dynamic sub-graph, graph density, MULBS, MULBS⁺