Test de propriété pour l'homomorphisme de graphes et d'hypergraphes

Nicolas Dalsass 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Dans ce rapport, nous nous intéressons à l'utilisation de testeurs de propriétés pour la recherche d'homomorphismes de graphes et d'hypergraphes. Après avoir montré quel genre de résultat nous pouvions attendre, nous étudions comment adapter les meilleurs testeurs connus à ce jour pour la résolution du problème k-max-csp, les limites de ces algorithmes utilisés dans le cadre de l'homomorphisme de graphes, et donnons de nouvelles bornes inférieures théoriques concernant ce genre d'algorithmes. En particulier, nous montrons que l'homomorphisme de graphe n'est pas effi cacement testable dans les modèles non-dense, ce que nous prouvons en généralisant le concept de graphe de Behrend.
Type de document :
Rapport
RR-11025, 2011, pp.23
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00618588
Contributeur : Jean-François Baget <>
Soumis le : vendredi 2 septembre 2011 - 11:26:17
Dernière modification le : vendredi 12 janvier 2018 - 01:54:38
Document(s) archivé(s) le : samedi 3 décembre 2011 - 02:23:12

Fichier

Testing_hypergraphs_homomorphi...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00618588, version 1

Citation

Nicolas Dalsass. Test de propriété pour l'homomorphisme de graphes et d'hypergraphes. RR-11025, 2011, pp.23. 〈lirmm-00618588〉

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

652