Cargando…
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k, we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous [Formula: see text] approximation in [Khuller, Pu...
| Autores principales: | , , |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7254917/ http://dx.doi.org/10.1007/978-3-030-48966-3_28 |