## 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 almost completely characterize the complexity of both the regular and the hop-bounded versions as a function of the strip width w.

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

Title of host publication | Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings |

Publisher | Springer |

Pages | 289-300 |

Number of pages | 12 |

ISBN (Print) | 978-3-3196-2126-5 |

DOIs | |

Publication status | Published - 2017 |

Event | 15th International Symposium on Algorithms and Data Structures (WADS 2017) - Memorial University of Newfoundland, St. John’s, Canada Duration: 31 Jul 2017 → 2 Aug 2017 Conference number: 15 http://www.wads.org/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 10389 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th International Symposium on Algorithms and Data Structures (WADS 2017) |
---|---|

Abbreviated title | WADS 2017 |

Country/Territory | Canada |

City | St. John’s |

Period | 31/07/17 → 2/08/17 |

Internet address |