The homogeneous broadcast problem in narrow and wide strips. I: Algorithms

DOI10.1007/S00453-019-00567-8zbMATH Open1421.68114OpenAlexW2928043237MaRDI QIDQ2415369FDOQ2415369

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

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00567-8

Recommendations

• The homogeneous broadcast problem in narrow and wide strips
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• Homogeneous 2-hop broadcast in 2D
• Homogeneous 2-Hops Broadcast in 2D
• The minimum broadcast range assignment problem on linear multi-hop wireless networks.

zbMATH Keywords

dominating setbroadcastrange assignmentunit-disk graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Unit disk graphs
• Parametrized complexity theory.
• Planar Formulae and Their Uses
• Computational geometry. Algorithms and applications.
• Automata, Languages and Programming
• Approximation schemes for covering and packing problems in image processing and VLSI
• On the hardness of range assignment problems
• Optimal Point Location in a Monotone Subdivision
• The steiner problem in graphs
• Shortest paths in intersection graphs of unit disks
• Geometric ad-hoc routing
• STACS 2004
• Fractional cascading. I: A data structuring technique
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Title not available (Why is that?)
• An ETH-Tight Exact Algorithm for Euclidean TSP
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Range assignment for energy efficient broadcasting in linear radio networks
• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• The dominating set problem in geometric intersection graphs
• The homogeneous broadcast problem in narrow and wide strips

Cited In (2)

• The homogeneous broadcast problem in narrow and wide strips
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds

This page was built for publication: The homogeneous broadcast problem in narrow and wide strips. I: Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415369)