Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072124
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:50:59 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:00:24 PM

Identifiers

  • HAL Id : inria-00072124, version 1

Collections

Citation

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

Share

Metrics

Record views

322

Files downloads

144