A New Formulation of Degree-Constrained Spanning Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

A New Formulation of Degree-Constrained Spanning Problems


Given a graph with edge-costs, searching for a minimum cost structure that connects a subset of vertices is a classic problem. We examine the spanning problems under constraints on the vertex degrees. Spanning tree solutions were generally investigated to solve them. However, for some applications the solution is not necessarily a sub-graph. Assuming that the degree constraint is due to the limited instantaneous capacity of the vertex and that the only other constraint on the spanning structure is its connectivity, we propose a reformulation of some spanning problems. To find the optimal coverage of the concerned vertices, an extension of the tree concept has been proposed. A hierarchy is obtained by a graph homomorphism between a tree and a target graph. Since this spanning structure may refer vertices (and edges) of the target graph several times, it is more flexible to satisfy constraints and nevertheless pertinent for network applications. Hierarchies correspond to the optimal solutions of the new problems. Here we resume our first promising results on the degree-constrained spanning hierarchies. They can solve network related cases where trees meeting the constraints do not exist. In other cases, hierarchies outperform trees. Furthermore, the degree constrained spanning hierarchy problem can be approximated within a constant ratio (while it is not possible with trees).
Fichier principal
Vignette du fichier
resumeMolnar.pdf (40.19 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

lirmm-01065963 , version 1 (18-09-2014)


  • HAL Id : lirmm-01065963 , version 1


Miklós Molnár, Sylvain Durand, Massinissa Merabet. A New Formulation of Degree-Constrained Spanning Problems. ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01065963⟩
236 View
259 Download


Gmail Facebook X LinkedIn More