Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching

Hussein Amro, Basel Fakhri, Amer E. Mouawad +1

Algorithms for finding minimum or bounded vertex covers in graphs use a branch-and-reduce strategy, which involves exploring a highly imbalanced search tree. Prior GPU solutions as…