Home // ICCGI 2013, The Eighth International Multi-Conference on Computing in the Global Information Technology // View article

Towards an Efficient Handling of the Maximum Triangle Packing Problem

Authors:
Youcef Abdelsadek
Francine Herrmann
Imed Kacem
Benoît Otjacques

Keywords: packing problems; maximum triangle packing; heuristics; computational study.

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 problem in combinatorics and it is well-known to be APX-hard. We propose two heuristics for this problem. The first is based on local substitutions, while the second uses a surrogate relaxation of the related integer linear program which is analog to a specific knapsack problem. A computational comparison of the two heuristics using randomly generated benchmarks has shown that the first heuristic outperforms the second heuristic regarding the obtained packing solutions and the respective computation times.

Pages: 249 to 252

Copyright: Copyright (c) IARIA, 2013

Publication date: July 21, 2013

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-283-7

Location: Nice, France

Dates: from July 21, 2013 to July 26, 2013