Optimal covering of rectangular grid graphs with tours of constrained length
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915160477663232 |
|---|---|
| author | Bereg, Sergey Capitán, Jesús Díaz-Bañez, José-Miguel Higes-López, José-Manuel Pérez-Cutiño, Miguel-Angel Sánchez, Vanesa Ventura, Inmaculada |
| author_facet | Bereg, Sergey Capitán, Jesús Díaz-Bañez, José-Miguel Higes-López, José-Manuel Pérez-Cutiño, Miguel-Angel Sánchez, Vanesa Ventura, Inmaculada |
| contents | Given a rectangular grid graph with a special vertex at a corner called base station, we study the problem of covering the vertices of the entire graph with tours that start and end at the base station and whose lengths do not exceed a given threshold, while minimizing a quality measure. We consider two objective functions: minimizing the number of tours and minimizing the sum of their lengths. We present an algorithm that computes the optimal solution for both objectives in linear time with respect to the grid size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13306 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal covering of rectangular grid graphs with tours of constrained length Bereg, Sergey Capitán, Jesús Díaz-Bañez, José-Miguel Higes-López, José-Manuel Pérez-Cutiño, Miguel-Angel Sánchez, Vanesa Ventura, Inmaculada Discrete Mathematics Computational Geometry Combinatorics G.2.1; F.2.2 Given a rectangular grid graph with a special vertex at a corner called base station, we study the problem of covering the vertices of the entire graph with tours that start and end at the base station and whose lengths do not exceed a given threshold, while minimizing a quality measure. We consider two objective functions: minimizing the number of tours and minimizing the sum of their lengths. We present an algorithm that computes the optimal solution for both objectives in linear time with respect to the grid size. |
| title | Optimal covering of rectangular grid graphs with tours of constrained length |
| topic | Discrete Mathematics Computational Geometry Combinatorics G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2502.13306 |