Cover Image

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Biedl, Therese, Gokhale, Prashant
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finding maximum matchings in RDV graphs efficiently
by: Biedl, Therese, et al.
Published: (2024)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
by: Biedl, Therese
Published: (2025)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
by: Herold, Martin G., et al.
Published: (2025)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
by: Browne, Reilly, et al.
Published: (2026)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
by: Biedl, Therese, et al.
Published: (2024)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

An Optimal Algorithm for Half-plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
by: Kumar, Manish, et al.
Published: (2026)

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)

Dominance for Containment Problems
by: Akram, Waseem, et al.
Published: (2022)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Maximizing Weighted Dominance in the Plane
by: Akram, Waseem, et al.
Published: (2024)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
by: Iacono, John, et al.
Published: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

On Planar Straight-Line Dominance Drawings
by: Angelini, Patrizio, et al.
Published: (2025)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
by: Park, Seongbin, et al.
Published: (2026)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Visibility Queries in Simple Polygons
by: Bhore, Sujoy, et al.
Published: (2026)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Top-k Stabbing Interval Queries
by: Akram, Waseem, et al.
Published: (2024)

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

Data Structures for Range Sorted Consecutive Occurrence Queries
by: Akram, Waseem, et al.
Published: (2024)

On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
by: Gudmundsson, Joachim, et al.
Published: (2022)

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

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)

Minimum-Weight Half-Plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
by: Liu, Gang, et al.
Published: (2024)