HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Robustness of a routing tree for the Push Tree Problem

Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:50:59 PM
Last modification on : Friday, February 4, 2022 - 3:20:14 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:00:24 PM


  • HAL Id : inria-00072124, version 1



Frédéric Havet. Robustness of a routing tree for the Push Tree Problem. RR-4464, INRIA. 2002. ⟨inria-00072124⟩



Record views


Files downloads