The homogeneous broadcast problem in narrow and wide strips

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

doi:10.1007/978-3-319-62127-2_25

The homogeneous broadcast problem in narrow and wide strips

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

^*Corresponding author for this work

Eindhoven University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Algorithms and Data Structures
Subtitle of host publication	15th International Symposium, WADS 2017, Proceedings
Publisher	Springer
Pages	289-300
Number of pages	12
ISBN (Print)	9783319621265
DOIs	https://doi.org/10.1007/978-3-319-62127-2_25
Publication status	Published - 2017
Event	15th International Symposium on Algorithms and Data Structures, WADS 2017 - St. John’s, Canada Duration: 31 Jul 2017 → 2 Aug 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10389 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	15th International Symposium on Algorithms and Data Structures, WADS 2017
Country/Territory	Canada
City	St. John’s
Period	31/07/17 → 2/08/17

Access to Document

10.1007/978-3-319-62127-2_25

HomogeneousFinal published version, 330 KBLicence: Taverne

Cite this

de Berg, M., Bodlaender, H. L., & Kisfaludi-Bak, S. (2017). The homogeneous broadcast problem in narrow and wide strips. In Algorithms and Data Structures: 15th International Symposium, WADS 2017, Proceedings (pp. 289-300). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10389 LNCS). Springer. https://doi.org/10.1007/978-3-319-62127-2_25

de Berg, Mark ; Bodlaender, Hans L. ; Kisfaludi-Bak, Sándor. / The homogeneous broadcast problem in narrow and wide strips. Algorithms and Data Structures: 15th International Symposium, WADS 2017, Proceedings. Springer, 2017. pp. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{592c80be4c714570b50a400618b2f920,

title = "The homogeneous broadcast problem in narrow and wide strips",

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.",

author = "{de Berg}, Mark and Bodlaender, {Hans L.} and S{\'a}ndor Kisfaludi-Bak",

year = "2017",

doi = "10.1007/978-3-319-62127-2_25",

language = "English",

isbn = "9783319621265",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "289--300",

booktitle = "Algorithms and Data Structures",

note = "15th International Symposium on Algorithms and Data Structures, WADS 2017 ; Conference date: 31-07-2017 Through 02-08-2017",

}

de Berg, M, Bodlaender, HL & Kisfaludi-Bak, S 2017, The homogeneous broadcast problem in narrow and wide strips. in Algorithms and Data Structures: 15th International Symposium, WADS 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10389 LNCS, Springer, pp. 289-300, 15th International Symposium on Algorithms and Data Structures, WADS 2017, St. John’s, Canada, 31/07/17. https://doi.org/10.1007/978-3-319-62127-2_25

The homogeneous broadcast problem in narrow and wide strips. / de Berg, Mark; Bodlaender, Hans L.; Kisfaludi-Bak, Sándor.
Algorithms and Data Structures: 15th International Symposium, WADS 2017, Proceedings. Springer, 2017. p. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10389 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The homogeneous broadcast problem in narrow and wide strips

AU - de Berg, Mark

AU - Bodlaender, Hans L.

AU - Kisfaludi-Bak, Sándor

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85025133899&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62127-2_25

DO - 10.1007/978-3-319-62127-2_25

M3 - Conference contribution

AN - SCOPUS:85025133899

SN - 9783319621265

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 289

EP - 300

BT - Algorithms and Data Structures

PB - Springer

T2 - 15th International Symposium on Algorithms and Data Structures, WADS 2017

Y2 - 31 July 2017 through 2 August 2017

ER -

de Berg M, Bodlaender HL, Kisfaludi-Bak S. The homogeneous broadcast problem in narrow and wide strips. In Algorithms and Data Structures: 15th International Symposium, WADS 2017, Proceedings. Springer. 2017. p. 289-300. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-62127-2_25

The homogeneous broadcast problem in narrow and wide strips

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this