On the approximability of some degree-constrained subgraph problems

Omid Amini 1 David Peleg 2 Stéphane Pérennes 3 Ignasi Sau 4 Saket Saurabh 5
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph G=(V,E). Let d>=2 be a fixed integer. The Maximumd-degree-bounded Connected Subgraph (MDBCS"d) problem takes as additional input a weight function @w:E->R^+, and asks for a subset E^'@?E such that the subgraph induced by E^' is connected, has maximum degree at most d, and @?"e"@?"E"^"'@w(e) is maximized. The Minimum Subgraph of Minimum Degree>=d (MSMD"d) problem involves finding a smallest subgraph of G with minimum degree at least d. Finally, the Dual Degree-densek-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)|@?k and the minimum degree in H is maximized.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, 160 (2), pp.1661-1679. 〈10.1016/j.dam.2012.03.025〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736702
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 18:04:14
Dernière modification le : lundi 5 novembre 2018 - 15:36:03

Lien texte intégral

Identifiants

Citation

Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh. On the approximability of some degree-constrained subgraph problems. Discrete Applied Mathematics, Elsevier, 2012, 160 (2), pp.1661-1679. 〈10.1016/j.dam.2012.03.025〉. 〈lirmm-00736702〉

Partager

Métriques

Consultations de la notice

432