Hierarchies for Constrained Partial Spanning Problems in Graphs

Abstract : The problem of minimal cost partial spanning trees is well known as the NP-complete Steiner problem in graphs. If there are constraints to respect by using some edges and nodes in the spanning structure or constraints on the required end to end (QoS) properties of the partial spanning structure, then the optimal structure can be different from a partial spanning tree. This paper present simple hierarchical spanning structures which correspond generally to the optimal solution. To illustrate the optimality of spanning hierarchies, two problems in communication networks, which are very usefull for multicast routing, are analyzed. In the first problem, the constraints are related to the physical capacity of the nodes in WDM networks. Namely, the analyzed example presents the case of sparse splitter nodes in optical networks. In the second example, the multi-constrained multicast routing is analyzed. In both cases, the optimal routing structure is a hierarchy. Since its computation is NP-complete, after the presentation of the computation difficulties some ideas on heuristic algorithms are discussed.
Type de document :
[Research Report] PI-1900, 2008, pp.47
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

Contributeur : Ist Rennes <>
Soumis le : lundi 25 août 2008 - 16:55:03
Dernière modification le : vendredi 16 novembre 2018 - 01:31:26
Document(s) archivé(s) le : mercredi 29 mars 2017 - 15:08:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00306687, version 2


Miklos Molnar. Hierarchies for Constrained Partial Spanning Problems in Graphs. [Research Report] PI-1900, 2008, pp.47. 〈inria-00306687v2〉



Consultations de la notice


Téléchargements de fichiers