Publikace na Matematicko-fyzikální fakulta |
2013
Abstrakt
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.