Test de propriété pour l'homomorphisme de graphes et d'hypergraphes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2011

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

Nicolas Dalsass
  • Function : Author
  • PersonId : 940768

Abstract

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.
Fichier principal
Vignette du fichier
Testing_hypergraphs_homomorphisms_2_.pdf (474.31 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00618588 , version 1 (02-09-2011)

Identifiers

  • HAL Id : lirmm-00618588 , version 1

Cite

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

Share

Gmail Mastodon Facebook X LinkedIn More