On Approximating the d-Girth of a Graph

Abstract : For a finite, simple, undirected graph G and an integer d ≥ 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted g d (G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdős et al. [13, 14] and Bollobás and Brightwell [7] over 20 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar.
Type de document :
Communication dans un congrès
SOFSEM'11: Theory and Practice of Computer Science, Slovakia. Springer Berlin Heidelberg, 6543, pp.467-481, 2011, LNCS. 〈10.1007/978-3-642-18381-2_39〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736705
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 18:13:00
Dernière modification le : vendredi 7 septembre 2018 - 14:04:02

Identifiants

Collections

Citation

David Peleg, Ignasi Sau, Mordechai Shalom. On Approximating the d-Girth of a Graph. SOFSEM'11: Theory and Practice of Computer Science, Slovakia. Springer Berlin Heidelberg, 6543, pp.467-481, 2011, LNCS. 〈10.1007/978-3-642-18381-2_39〉. 〈lirmm-00736705〉

Partager

Métriques

Consultations de la notice

139