carrier image

Solving the Maximum Weight Independent Set Problem: Application to Indirect Hexahedral Mesh Generation

Verhetsel, Kilian, Jeanne Pellerin, Amaury Johnen, Jean-François Remacle

Research Notes, 26th International Meshing Roundtable, Sandia National Laboratories, September 18-21 2017


26th International Meshing Roundtable
Barcelona, Spain
September 18-21, 2017

Kilian Verhetsel, Université catholique de Louvain, BE,
Jeanne Pellerin, Université catholique de Louvain, BE,
Amaury Johnen, Université catholique de Louvain, BE,
Jean-François Remacle, Université catholique de Louvain, BE,

Research Note Abstract
Indirect hex-dominant meshing methods rely on the choice of a subset of compatible hexahedra among a large set of candidate hexahedra generated by combining tetrahedra. We propose a new parallel algorithm to choose this subset of compatible hexahedra. Our algorithm computes a near-optimal solution to the Maximum Weight Independent Set problem on the incompatibility graph of the candidate hexahedra. An initial solution computed with a greedy algorithm is iteratively improved by optimizing subgraphs containing up to a few hundred vertices. This procedure uses a branch and bound algorithm and is done in parallel on multiple disjoint subgraphs. First results are presented on large sets of candidate hexahedra and we show that meshes containing up to 10\% more hexahedra than greedy methods can be computed within a few seconds.

Download Full Paper (PDF)

Contact author(s) or publisher for availability and copyright information on above referenced article