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-Boun...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.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.62162066the Open Funding of Engineering Research Center of Cyberspace of Ministry of Education of China under Grant No.WLKJAQ202011010+1 种基金the Education Department Funding of Yunnan Province of China under Grant No.2021J0006the 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.
