The homogeneous broadcast problem in narrow and wide strips

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

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

The homogeneous broadcast problem in narrow and wide strips

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

Algorithms

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 - 15th International Symposium, WADS 2017, Proceedings
Publisher	Springer
Pages	289-300
Number of pages	12
ISBN (Print)	978-3-3196-2126-5
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) - 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	http://www.wads.org/

Access to Document

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

Cite this

@inproceedings{4f422bf2879b4194831237c0dd4416ee,

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}, M. and H.L. Bodlaender and S. Kisfaludi-Bak",

year = "2017",

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

language = "English",

isbn = "978-3-3196-2126-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "289--300",

booktitle = "Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings",

address = "Germany",

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

url = "http://www.wads.org/",

}

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, vol. 10389, Springer, pp. 289-300, 15th International Symposium on Algorithms and Data Structures (WADS 2017), St. John’s, Newfoundland and Labrador, 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, M.; Bodlaender, H.L.; Kisfaludi-Bak, S.
Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings. Springer, 2017. p. 289-300 (Lecture Notes in Computer Science; Vol. 10389).

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

AU - Bodlaender, H.L.

AU - Kisfaludi-Bak, S.

N1 - Conference code: 15

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 - 978-3-3196-2126-5

T3 - Lecture Notes in Computer Science

SP - 289

EP - 300

BT - Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings

PB - Springer

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

Y2 - 31 July 2017 through 2 August 2017

ER -

The homogeneous broadcast problem in narrow and wide strips

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this