A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem

We present a new highly parallel algorithm for fast determination of near-optimal solutions to the NP-hard problem of identifying a maximum distance-2 matching in arbitrary graphs. This problem, known as D2EMIS, has important applications such as determining the maximum capacity of the media access (MAC) layer in wireless ad-hoc networks [1]. It can also be seen as a maximum 2-packing problem [2] on the edge-to-vertex dual graph of the original graph. Our algorithm extends the GRASP [3] philosophy in that partial solutions are constructed by adding in a greedy adaptive manner the “best” nodes that can be found; however, when there are multiple alternatives that can be selected in an iteration, the algorithm branches into as many paths as there are (greedy) alternatives. The algorithm, using appropriate bounds to prune partial solutions that cannot be optimal, produces very fast near-optimal solutions that compare very well against other distributed algorithms and random greedy heuristics proposed before or variants thereof, or exact methods (Integer Programming or Maximum Satisfiability state-of-the-art solvers).