The k-hop connected dominating set problem: approximation algorithms and hardness results
Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of f...
| Autor principal: | |
|---|---|
| Formato: | doctoralThesis |
| Idioma: | eng |
| Publicado em: |
2017
|
| Texto completo: | https://doi.org/10.11606/T.45.2017.tde-27062017-101521 |
| País: | Brasil |
| Oai: | oai:teses.usp.br:tde-27062017-101521 |