Solving the maximum weight independent set problem : application to indirect hex-mesh generation

We propose a heuristic method to find independent sets of large weight in graphs, used as part of an algorithm for indirect generation of hex-dominant meshes. Our method computes an initial solution using a local search algorithm. This algorithm was implemented using priority queues to select which action should be performed at each iteration in order to improve its performances. The initial solution is then iteratively improved by finding the optimal solution of the problem for subgraphs of up to a few hundred vertices. For this purpose, we use a branch and bound solver. This solver partitions the vertex set of the graph into cliques at each node of the search tree. This partition allows for the computation of an upper bound on the solution, which is used to reduce the number of solutions enumerated by the algorithm. We ran our algorithm on graphs of more than one million vertices, and showed that it produces better results than the greedy methods used in existing indirect meshing algorithms.