Approximation of the Degree-Constrained Minimum Spanning Hierarchies

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 : Degree-constrained spanning problems are well known and are mainly used to solve capacity constrained routing problems. The degree-constrained spanning tree problems are NP-hard and computing the minimum cost spanning tree is not approximable. Often, applications (such as some degree-constrained communications) do not need trees as solutions. Recently, a more flexible, connected, graph related structure called hierarchy was proposed to span a set of vertices under constraints. This structure permits a new formulation of some degree-constrained spanning problems. In this paper we show that although the newly for- mulated problem is still NP-hard, it is approximable with a constant ratio. In the worst case, this ratio is bounded by 3/2. We provide a sim- ple heuristic and prove its approximation ratio is the best possible for any algorithm based on a minimum spanning tree.
Type de document :
Communication dans un congrès
SIROCCO: Structural Information and Communication Complexity, Jul 2014, Takayama, Japan. Springer International Publishing, 21th International Colloquium on Structural Information and Communication Complexity July 23 - 25, 2014, Hida Takayama, Japan, LNCS (8576), pp.96-107, 2014, 〈https://sites.google.com/site/sirocco2014japan/home〉. 〈10.1007/978-3-319-09620-9_9〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01056259
Contributeur : Sylvain Durand <>
Soumis le : lundi 18 août 2014 - 12:41:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Miklós Molnár, Sylvain Durand, Massinissa Merabet. Approximation of the Degree-Constrained Minimum Spanning Hierarchies. SIROCCO: Structural Information and Communication Complexity, Jul 2014, Takayama, Japan. Springer International Publishing, 21th International Colloquium on Structural Information and Communication Complexity July 23 - 25, 2014, Hida Takayama, Japan, LNCS (8576), pp.96-107, 2014, 〈https://sites.google.com/site/sirocco2014japan/home〉. 〈10.1007/978-3-319-09620-9_9〉. 〈lirmm-01056259〉

Partager

Métriques

Consultations de la notice

124