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...
| Main Author: | |
|---|---|
| Format: | doctoralThesis |
| Language: | eng |
| Published: |
2017
|
| Online Access: | https://doi.org/10.11606/T.45.2017.tde-27062017-101521 |
| Country: | Brazil |
| Oai: | oai:teses.usp.br:tde-27062017-101521 |