The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)2934-2962
Number of pages29
JournalAlgorithmica
Volume81
Issue number7
DOIs
Publication statusPublished - 1 Jul 2019

Keywords

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

Fingerprint

Dive into the research topics of 'The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms'. Together they form a unique fingerprint.

Cite this