A Generalization of Distance Domination
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_ | 1866909860618043392 |
|---|---|
| author | Muth, Alicia Neimand, E. Dov |
| author_facet | Muth, Alicia Neimand, E. Dov |
| contents | Expanding on the graph theoretic ideas of k-component order connectivity and distance-l domination, we present a quadratic-complexity algorithm that finds a tree's minimum failure-set cardinality, i.e., the minimum cardinality any subset of the tree's vertices must have so that all clusters of vertices further away than some l do not exceed a cardinality threshold. Applications of solutions to the expanded problems include choosing service center locations so that no large neighborhoods are excluded from service, while reducing the redundancy inherent in distance domination problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18066 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Generalization of Distance Domination Muth, Alicia Neimand, E. Dov Data Structures and Algorithms Combinatorics 05C05, 05C12, 05C40 G.2.2 Expanding on the graph theoretic ideas of k-component order connectivity and distance-l domination, we present a quadratic-complexity algorithm that finds a tree's minimum failure-set cardinality, i.e., the minimum cardinality any subset of the tree's vertices must have so that all clusters of vertices further away than some l do not exceed a cardinality threshold. Applications of solutions to the expanded problems include choosing service center locations so that no large neighborhoods are excluded from service, while reducing the redundancy inherent in distance domination problems. |
| title | A Generalization of Distance Domination |
| topic | Data Structures and Algorithms Combinatorics 05C05, 05C12, 05C40 G.2.2 |
| url | https://arxiv.org/abs/2510.18066 |