TCS Journal 2007 Journal Article
Communication tree problems
- Carme Àlvarez
- Rafel Cases
- Josep Díaz
- Jordi Petit
- Maria Serna
In this paper, we deal with the problem of constructing optimal communication trees satisfying given communication requirements. We consider two constant degree tree communication models and several cost measures. First, we analyze whether a tree selected at random provides a good randomized approximation algorithm, and we show that such a construction fails for some of the measures. Secondly, we provide approximation algorithms for the case in which the communication requirements are given by a random graph in two different random models, namely the classical G n, p and random geometric graphs. Finally, we conclude with some open problems.