Finding maximum matchings in RDV graphs efficiently
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911907913400320 |
|---|---|
| author | Biedl, Therese Gokhale, Prashant |
| author_facet | Biedl, Therese Gokhale, Prashant |
| contents | In this paper, we study the maximum matching problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. We show that this problem can be reduced to a problem of testing (repeatedly) whether a vertical segment intersects one of a dynamically changing set of horizontal segments, which in turn reduces to an orthogonal ray shooting query. Using a suitable data structure, we can therefore find a maximum matching in $O(n\log n)$ time (presuming a linear-sized representation of the graph is given), i.e., without even looking at all edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03632 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding maximum matchings in RDV graphs efficiently Biedl, Therese Gokhale, Prashant Computational Geometry Data Structures and Algorithms In this paper, we study the maximum matching problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. We show that this problem can be reduced to a problem of testing (repeatedly) whether a vertical segment intersects one of a dynamically changing set of horizontal segments, which in turn reduces to an orthogonal ray shooting query. Using a suitable data structure, we can therefore find a maximum matching in $O(n\log n)$ time (presuming a linear-sized representation of the graph is given), i.e., without even looking at all edges. |
| title | Finding maximum matchings in RDV graphs efficiently |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.03632 |