Title: Approximation Algorithms for Group Communication Networks
Abstract: Consider a communication network in which parties are supposed to distribute information within the network. The problem of planning communication networks arises in many real-world applications, e.g., the design of server clusters or sensor networks. A natural way to model these networks is to represent the parties by nodes of a graph and the communication links between parties by edges. Problems that concern the distribution of messages in networks are often affiliated with the computation of sparse subgraphs of the underlying network graph.
We are particularly interested in approximation algorithms for concurrent multicasting, which is a generalization for both multicasting and gossiping. To the best of our knowledge, we provide the first non-trivial upper bounds for concurrent multicasting in the radio model. Further, we introduce two network design problems, namely the minimum degree diameter-bounded network problem and the minimum total-degree diameter-bounded group network problem, which are both related to concurrent multicasting in the telephone model. Our results also have implications for the computation of graph spanners with small maximum degree.
