Branch-and-bound algorithm for the maximum triangle packing problem |
| |
| Affiliation: | 1. e-Science Research Unit, Environmental Research and Innovation department, Luxembourg Institute of Science and Technology, Belvaux, Luxembourg;2. Laboratoire de Conception, Optimisation et Modélisation des Systèmes (LCOMS EA 7306), Université de Lorraine, Metz, France;1. Faculty of Science, Kunming University of Science and Technology, Kunming 650093, China;2. School of Nuclear Engineering and Geophysics, East China Institute of Technology, Nanchang 330013, Jiangxi, China;3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;4. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;5. Department of Statistics, Feng Chia University, Taichung, Taiwan;1. School of Automation, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, PR China;2. DRUID, IRISA, University of Rennes 1, Rue E. Branly, 22300 Lannion, France;1. School of Quantitative Sciences, CAS, Universiti Utara Malaysia, 06010 Kedah, Malaysia;2. School of Mathematical Sciences, Universiti Sains Malaysia, Penang, Malaysia;3. Networking & Computer Company, 1820 San Pedro Dr. NE, Albuquerque, NM 87110, United States;4. School of Mathematics, Shahid Bahonar University, Kerman, Iran;1. “Simion Stoilow” Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, RO-014700, Bucharest, Romania;2. CRAN–CNRS UMR 7039, Universite de Lorraine, France |
| |
| Abstract: | This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time. |
| |
| Keywords: | Maximum triangle packing Lower bounds Upper bounds Branch-and-bound algorithm Computational study |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
