On the minimum edge cover and vertex partition by quasi-cliques problems

Résumé : Un $\gamma$-quasi-clique, pour $0<\gamma< 1$, dans un graphe simple non-orienté est un sous-ensemble de sommets dont le sous-graphe induit a une densité d'arêtes supérieure ou égale à $\gamma$. Un ensemble de $\gamma$-quasi-cliques couvrant toutes les arêtes d'un graphe est appelé une couverture par des $\gamma$-quasi-cliques. Le problème de couverture minimale par des $\gamma$-quasi-cliques consiste à trouver une couverture par des $\gamma$-quasi-cliques ayant le plus petit nombre de quasi-cliques. Une partition des sommets d'un graphe par des quasi-cliques est un ensemble de $\gamma$-quasi-cliques telle que chaque sommet du graphe appartient à un seul quasi-clique de l'ensemble. Le problème de partition minimale par des $\gamma$-quasi-cliques consiste à trouver une partition par des $\gamma$-quasi-cliques ayant le plus petit nombre de quasi-cliques. Nous démontrons que les problèmes de décision associés aux problèmes de couverture minimale et partition minimale par des $\gamma$-quasi-cliques sont NP-complets pour tout $\gamma$ satisfaisant $0<\gamma<1$ fixé.
Type de document :
Rapport
[Research Report] RR-8255, INRIA. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00795429
Contributeur : Equipe Roma <>
Soumis le : mardi 5 mars 2013 - 09:47:55
Dernière modification le : mardi 16 janvier 2018 - 15:34:57
Document(s) archivé(s) le : dimanche 2 avril 2017 - 07:26:25

Fichier

RR-8255.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00795429, version 2

Collections

Citation

Oguz Kaya, Enver Kayaaslan, Bora Uçar. On the minimum edge cover and vertex partition by quasi-cliques problems. [Research Report] RR-8255, INRIA. 2013. 〈hal-00795429v2〉

Partager

Métriques

Consultations de la notice

428

Téléchargements de fichiers

1003