## Abstract

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let s∈ P be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, s must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width w. We describe several algorithms for both the regular and the hop-bounded versions, and show that both problems are solvable in polynomial time in strips of small constant width. These results complement the hardness results in a companion paper (de Berg et al. in Algorithmica, 2017).

Original language | English |
---|---|

Pages (from-to) | 2934-2962 |

Number of pages | 29 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 7 |

DOIs | |

Publication status | Published - 1 Jul 2019 |

## Keywords

- Broadcast
- Dominating set
- Range assignment
- Unit-disk graph