The homogeneous broadcast problem in narrow and wide strips. I: Algorithms
From MaRDI portal
Publication:2415369
DOI10.1007/s00453-019-00567-8zbMath1421.68114OpenAlexW2928043237MaRDI QIDQ2415369
Sándor Kisfaludi-Bak, Hans L. Bodlaender, Mark T. de Berg
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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range assignment for energy efficient broadcasting in linear radio networks
- Fractional cascading. I: A data structuring technique
- Unit disk graphs
- Shortest paths in intersection graphs of unit disks
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The homogeneous broadcast problem in narrow and wide strips
- Parametrized complexity theory.
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Geometric ad-hoc routing
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- On the hardness of range assignment problems
- Optimal Point Location in a Monotone Subdivision
- Approximation schemes for covering and packing problems in image processing and VLSI
- Planar Formulae and Their Uses
- The Dominating Set Problem in Geometric Intersection Graphs
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- STACS 2004
- The steiner problem in graphs
- Automata, Languages and Programming
- An ETH-Tight Exact Algorithm for Euclidean TSP
