Skip to Main content Skip to Navigation
Conference papers

A New Formulation of Degree-Constrained Spanning Problems

Miklós Molnár 1 Sylvain Durand 1, 2 Massinissa Merabet 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 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).
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
Contributor : Miklos Molnar <>
Submitted on : Thursday, September 18, 2014 - 5:49:53 PM
Last modification on : Wednesday, October 7, 2020 - 10:04:12 AM
Long-term archiving on: : Friday, December 19, 2014 - 2:20:44 PM


Publisher files allowed on an open archive


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



Record views


Files downloads