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.
Document type :
Reports
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00618588
Contributor : Jean-François Baget <>
Submitted on : Friday, September 2, 2011 - 11:26:17 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Saturday, December 3, 2011 - 2:23:12 AM

File

Testing_hypergraphs_homomorphi...
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00618588, version 1

Collections

Citation

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

Share

Metrics

Record views

403

Files downloads

958