Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

Abstract : For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.57--70
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972307
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:07:45
Dernière modification le : mardi 5 mai 2015 - 10:48:58
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:30:42

Fichier

494-3180-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972307, version 1

Collections

Citation

Hamamache Kheddouci, Olivier Togni. Bounds for minimum feedback vertex sets in distance graphs and circulant graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.57--70. 〈hal-00972307〉

Partager

Métriques

Consultations de
la notice

320

Téléchargements du document

160