Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917189906333696 |
|---|---|
| author | Biedl, Therese Gokhale, Prashant |
| author_facet | Biedl, Therese Gokhale, Prashant |
| contents | In this paper, we study the dominating set problem in \emph{RDV graphs}, a graph class that lies between interval graphs and chordal graphs and is defined as the \textbf{v}ertex-intersection graphs of \textbf{d}ownward paths in a \textbf{r}ooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an $n$-vertex RDV graph, using priority search trees, in $O(n\log n)$ time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph $O(n\log n)$ time (presuming a linear-sized representation of the graph is given). The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in $O(n)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04626 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs Biedl, Therese Gokhale, Prashant Data Structures and Algorithms Computational Geometry In this paper, we study the dominating set problem in \emph{RDV graphs}, a graph class that lies between interval graphs and chordal graphs and is defined as the \textbf{v}ertex-intersection graphs of \textbf{d}ownward paths in a \textbf{r}ooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an $n$-vertex RDV graph, using priority search trees, in $O(n\log n)$ time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph $O(n\log n)$ time (presuming a linear-sized representation of the graph is given). The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in $O(n)$ time. |
| title | Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2601.04626 |