Hierarchies to Solve Constrained Connected Spanning Problems

Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a graph and a set of vertices, searching for a connected and minimum cost structure which spans the vertices is a classic problem. When no constraints are applied, the minimum cost spanning structure is a sub-graph corresponding to a tree. If all the vertices in the graph should be spanned the problem is referred to as minimum spanning tree (MST) construction and polynomial time algorithms exist to find these trees. On the contrary, if only a subset of vertices is concerned then the problem becomes NP-hard. The computation of partial minimum spanning trees is known as the Steiner problem in graphs. In some cases, constraints are present in the problem formulation: several constrained spanning and Steiner problems are known. Generally,only the tree-like spanning solutions were investigated. In this paper, we demonstrate that the cost optimal spanning structure in constrained situations is not necessarily a spanning tree. To find the optimal spanning structure, we propose the extension of the tree concept and we define the hierarchies. A hierarchy is obtained by a graph homomorphism from a tree to a given target graph which may refer vertices (and so edges) of the target graph several times. We prove that generally (including constrained spanning problems) the minimum cost connected structure spanning a set of vertices is a spanning hierarchy. To justify the introduction of spanning hierarchies, some spanning problems with various constraints are presented. The constrained spanning problems are frequently NP-hard and intensive research will be required to explore the properties of the optimal spanning hierarchies and to find exact and efficient heuristic algorithms to solve these newly formulated problems.
Type de document :
Rapport
RR-11029, 2011, pp.26
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00619806
Contributeur : Miklos Molnar <>
Soumis le : mardi 6 septembre 2011 - 18:05:54
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 7 décembre 2011 - 02:40:36

Fichier

molnar_hierarchy.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00619806, version 1

Collections

Citation

Miklós Molnár. Hierarchies to Solve Constrained Connected Spanning Problems. RR-11029, 2011, pp.26. 〈lirmm-00619806〉

Partager

Métriques

Consultations de la notice

343

Téléchargements de fichiers

276