Parallel Bounded Search for the Maximum Clique Problem  

作　　者：江华 白珂 刘海姣 李初民 Felip Manya 付樟华 Hua Jiang;Ke Bai;Hai-Jiao Liu;Chu-Min Li;Felip Manya;Zhang-Hua Fu(Engineering Research Center of Cyberspace,Yunnan University,Kunming 650500,China;School of Software,Yunnan University,Kunming 650500,China;Laboratory of Modeling,Information and Systems,University of Picardie Jules Verne,Amiens 80039,France;Artificial Intelligence Research Institute,Spanish National Research Council,Catalonia 08193,Spain;Shenzhen Institute of Artificial Intelligence and Robotics for Society,Shenzhen 518000,China;Institute of Robotics and Intelligent Manufacturing,Chinese University of Hong Kong,Shenzhen 518000,China)

机构地区：[1]Engineering Research Center of Cyberspace,Yunnan University,Kunming 650500,China [2]School of Software,Yunnan University,Kunming 650500,China [3]Laboratory of Modeling,Information and Systems,University of Picardie Jules Verne,Amiens 80039,France [4]Artificial Intelligence Research Institute,Spanish National Research Council,Catalonia 08193,Spain [5]Shenzhen Institute of Artificial Intelligence and Robotics for Society,Shenzhen 518000,China [6]Institute of Robotics and Intelligent Manufacturing,Chinese University of Hong Kong,Shenzhen 518000,China

出　　处：《Journal of Computer Science & Technology》2023年第5期1187-1202,共16页计算机科学技术学报（英文版）

基　　金：supported by the National Natural Science Foundation of China under Grant No.62162066;the Open Funding of Engineering Research Center of Cyberspace of Ministry of Education of China under Grant No.WLKJAQ202011010;the Education Department Funding of Yunnan Province of China under Grant No.2021J0006;the Spanish AEI project PID2019-111544GB-C2.

摘　　要：Given an undirected graph,the Maximum Clique Problem(MCP)is to find a largest complete subgraph of the graph.MCP is NP-hard and has found many practical applications.In this paper,we propose a parallel Branch-and-Bound(BnB)algorithm to tackle this NP-hard problem,which carries out multiple bounded searches in parallel.Each search has its upper bound and shares a lower bound with the rest of the searches.The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound.We describe the implementation of our highly scalable and efficient parallel MCP algorithm,called PBS,which is based on a state-of-the-art sequential MCP algorithm.The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances.The results show that PBS achieves a near-linear speedup on most DIMACS instances and a superlinear speedup on most BHOSLIB instances.Finally,we give a detailed analysis that explains the good speedups achieved for the tested instances.

关 键 词：Branch-and-Bound(BnB) maximum clique problem(MCP) parallel search 

分 类 号：O17[理学—数学]