An exact algorithm for the maximum k-club problem in an undirected graph |
| |
| Affiliation: | 1. Department of Decision Sciences and MIS, Concordia University, 1455 de Maisonneuve boulevard West, Montréal, Canada H3G 1M8;2. Centre de recherche sur les transports, Université de Montréal, Case postale 6128, Succursale “Centre-ville”, Montréal, Canada H3C 3J7;3. GERAD and École des Hautes Études Commerciales, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Que., Canada H3T 2A7;4. Département de génie électrique et de génie informatique, École Polytechnique de Montréal, Case Postale 6079, Succursale “Centre-ville”, Montréal, Canada H3C 3J7;1. Gianforte School of Computing, Montana State University, Bozeman, MT 59717-3880, USA;2. Department of Computer Science, Beijing University of Chemical Technology, Beijing, China;3. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China;4. School of Economics and Management, Beijing University of Chemical Technology, Beijing, China;1. Università degli Studi di Bergamo, Bergamo, Italy;2. Ben-Gurion University of the Negev, Be''er Sheva, Israel |
| |
| Abstract: | In this paper, we prove that the maximum k-club problem (MkCP) defined on an undirected graph is NP-hard. We also give an integer programming formulation for this problem as well as an exact branch-and-bound algorithm and computational results on instances involving up to 200 vertices. Instances defined on very dense graphs can be solved to optimality within insignificant computing times. When k=2, the most difficult cases appear to be those where the graph density is around 0.15. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
