Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
From MaRDI portal
Publication:5042449
DOI10.1007/978-3-030-42071-0_5OpenAlexW3020143409MaRDI QIDQ5042449
Sándor Kisfaludi-Bak, Mark T. de Berg
Publication date: 19 October 2022
Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-42071-0_5
Related Items (1)
Cites Work
- Sphere and dot product representations of graphs
- Safe reduction rules for weighted treewidth
- Unit disk graph recognition is NP-hard
- The complexity of dominating set in geometric intersection graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
- On Geometric Set Cover for Orthants
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- Parameterized Algorithms
- How Does Object Fatness Impact the Complexity of Packing in d Dimensions
- On the complexity of \(k\)-SAT
This page was built for publication: Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
