A new exact maximum clique algorithm for large and massive sparse graphs |
| |
| Affiliation: | 1. Center for Automation and Robotics (UPM-CSIC), Jose Gutiérrez Abascal 2, Madrid 28006, Spain;2. Center for Applied Optimization, University of Florida, 401 Weil Hall, P.O. Box 116595, Gainesville, FL 32611-6595, USA;3. Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, 136 Rodionova, Nizhny Novgorod, 603093, Russian Federation;1. Mesoscopic and Multilayers Structures Laboratory, Department of Physics, Faculty of Science, University of Dschang, P.O. Box 479 Dschang, Cameroon;2. Department of Physics, Higher Teacher Training College Bambili, The University of Bamenda, P.O. Box 39 Bamenda, Cameroon;3. Laboratory of Electronics and Signal Processing, Department of Physics, Faculty of Science, University of Dschang, P.O. Box 67 Dschang, Cameroon;1. University of Pisa, Largo Bruno Pontecorvo 3, Pisa, 56127, Italy;2. The Advanced Algorithms Research Laboratory, The University of Electro-Communications, Chofugaoka 1–5–1, Chofu, Tokyo, 182–8585, Japan;1. Dipartimento di Economia e Management, Universitá di Brescia, Italy;2. Departamento de Estadística e Investigación Operativa, Universidad de Valencia, Spain;3. Departamento de Matemáticas para la Economía y la Empresa, Universidad de Valencia, Spain;4. Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, Spain |
| |
| Abstract: | This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds. |
| |
| Keywords: | Branch and bound Bitstring Massive Sparse Maximum clique |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
