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.
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00619806
Contributor : Miklos Molnar <>
Submitted on : Tuesday, September 6, 2011 - 6:05:54 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Wednesday, December 7, 2011 - 2:40:36 AM

File

molnar_hierarchy.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

390

Files downloads

383