Buchumschlag

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	de Berg, Mark, Kisfaludi-Bak, Sándor
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
von: Koana, Tomohiro, et al.
Veröffentlicht: (2024)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

Structure and Independence in Hyperbolic Uniform Disk Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

Maximizing Weighted Dominance in the Plane
von: Akram, Waseem, et al.
Veröffentlicht: (2024)

Touring a Sequence of Orthogonal Polygons
von: Casel, Katrin, et al.
Veröffentlicht: (2026)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
von: Browne, Reilly, et al.
Veröffentlicht: (2026)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Smallest Intersecting Balls
von: Zheng, Jiaqi, et al.
Veröffentlicht: (2024)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
von: Singh, Sipra
Veröffentlicht: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
von: de Berg, Mark, et al.
Veröffentlicht: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Dominance for Containment Problems
von: Akram, Waseem, et al.
Veröffentlicht: (2022)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
von: Focke, Jacob, et al.
Veröffentlicht: (2022)

Minimum-Weight Half-Plane Hitting Set
von: Liu, Gang, et al.
Veröffentlicht: (2025)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2026)

On Planar Straight-Line Dominance Drawings
von: Angelini, Patrizio, et al.
Veröffentlicht: (2025)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Unit-length Rectangular Drawings of Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2022)

Computing Maximum Cliques in Unit Disk Graphs
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2025)

Shortest Path Separators in Unit Disk Graphs
von: Harb, Elfarouk, et al.
Veröffentlicht: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
von: Goyal, Dishant, et al.
Veröffentlicht: (2024)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
von: Duraj, Lech, et al.
Veröffentlicht: (2023)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2020)

Subcoloring of (Unit) Disk Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
von: Bonamy, Marthe, et al.
Veröffentlicht: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
von: Nekrich, Yakov, et al.
Veröffentlicht: (2026)

Exact Optimization for Minimum Dominating Sets
von: Zhu, Enqiang, et al.
Veröffentlicht: (2025)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)