Solving the Maximum Weight Independent Set Problem: Application to Indirect Hexahedral Mesh Generation
(2017) 26th International Meshing Roundtable — Location: Barcelona (18.September.2017)
Files
ResearchNoteIMR2017.pdf
Open Access - Adobe PDF
- 2.38 MB
Details
- Authors
- 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.
- Affiliations
Citations
Verhetsel, K., Pellerin, J., Johnen, A., & Remacle, J.-F. (2017). Solving the Maximum Weight Independent Set Problem: Application to Indirect Hexahedral Mesh Generation. 26th International Meshing Roundtable, Barcelona. https://hdl.handle.net/2078.5/239939