Robustness of a routing tree for the Push Tree Problem

Description

The Push Tree problem contains elements from both the Steiner Tree and Shortest Path problem. It deals with the trade-offs between the push and pull mechanism used in information distribution and retrieval. In , a two step approach for the Push Tree Problem was proposed. In the first step, a «good» spanning tree (called routing tree) is constructed and then the problem is solved in this particular tree. Finding a routing tree is NP-hard but the second step may be performed easily, thus the idea is to use the routing tree as a (semi-) stable infrastructure and to perform adaptations to changing information patterns inside the routing tree. In this paper, we study the robustness of a routing tree when the information requests disappear at some nodes.

Additional details