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

DOI10.1007/S00453-019-00567-8MaRDI QIDQ2415369zbMATH OpenOpenAlexFDO

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

Publication date 21 May 2019

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

Cites work

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

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)