Publication at Faculty of Mathematics and Physics |
2013
Abstract
In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree T and need to be transmitted to the root of T.We address the special case of the problem when T is a chain network. For the online case, we present a 5-competitive algorithm and give a lower bound of 3.618, improving the previous bounds of 8 and 2, respectively.
Furthermore, for the offline version, we give a polynomial-time algorithm that computes the optimum solution.