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

DOI10.1007/s00453-019-00561-0zbMath1421.68115OpenAlexW2923900523MaRDI QIDQ2415370

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-00561-0

zbMATH Keywords

dominating setbroadcastunit disk graphrange assignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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
• The homogeneous broadcast problem in narrow and wide strips
• Parametrized complexity theory.
• Geometric ad-hoc routing
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Planar Formulae and Their Uses
• The limited blessing of low dimensionality
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
• Parameterized Complexity of Independent Set in H-Free Graphs.
• The Dominating Set Problem in Geometric Intersection Graphs
• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• Parameterized Algorithms
• On the complexity of \(k\)-SAT