A Reference Implementation of a Greedy Coverage-Based Relay Selection Algorithm

Selecting a small subset of relay (forwarder) nodes is a fundamental problem in multi-hop networks, since unnecessary relays lead to redundant broadcast transmissions. This paper presents a concise reference implementation of a coverage-based multipoint relay selection algorithm that guarantees full two-hop neighborhood coverage while limiting the number of relays. The method follows a two-stage greedy process: relays are first selected when they are the only nodes capable of reaching specific two-hop neighbors; remaining uncovered neighbors are then handled through iterative coverage maximization. The implementation is evaluated as a standalone graph algorithm using randomized stress tests, focusing on coverage correctness, relay-set size, and runtime across a range of network densities, including sparse and borderline-connected cases, and demonstrates consistent coverage correctness across all evaluated scenarios. While inspired by the Multipoint Relay (MPR) concept in the Optimized Link-State Routing (OLSR) protocol, the formulation is protocol-independent. The reference implementation is released as open-source code to support reproducibility and reuse.