The homogeneous broadcast problem in narrow and wide strips

M. de Berg, H.L. Bodlaender, S. Kisfaludi-Bak

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 almost completely characterize the complexity of both the regular and the hop-bounded versions as a function of the strip width w.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
PublisherSpringer
Pages289-300
Number of pages12
ISBN (Print)978-3-3196-2126-5
DOIs
Publication statusPublished - 2017
Event15th International Symposium on Algorithms and Data Structures (WADS 2017) - Memorial University of Newfoundland, St. John’s, Canada
Duration: 31 Jul 20172 Aug 2017
Conference number: 15
http://www.wads.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10389
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Symposium on Algorithms and Data Structures (WADS 2017)
Abbreviated titleWADS 2017
CountryCanada
CitySt. John’s
Period31/07/172/08/17
Internet address

Fingerprint Dive into the research topics of 'The homogeneous broadcast problem in narrow and wide strips'. Together they form a unique fingerprint.

Cite this