Zobrazeno 1 - 10
of 10
pro vyhledávání: '"largeur de clique"'
Autor:
Bergougnoux, Benjamin
Durant ces dernières décennies, d'importants efforts et beaucoup de café ont été dépensés en vue de caractériser les instances faciles des problèmes NP-difficiles. Dans ce domaine de recherche, une approche s'avère être redoutablement effi
Externí odkaz:
http://www.theses.fr/2019CLFAC025/document
Autor:
Courcelle, Bruno, Engelfriet, Joost
Publikováno v:
Cambridge University Press, pp.728, 2012, Encyclopedia of Mathematics and its applications, Vol. 138, 978-0-521-89833-1
The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical la
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94f3fa463f0fe8f24b3b603cc28c80b6
https://doi.org/10.1017/cbo9780511977619
https://doi.org/10.1017/cbo9780511977619
Autor:
Bagan, Guillaume
Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour les
Externí odkaz:
http://tel.archives-ouvertes.fr/tel-00424232
http://tel.archives-ouvertes.fr/docs/00/42/42/32/PDF/these.pdf
http://tel.archives-ouvertes.fr/docs/00/42/42/32/PDF/these.pdf
Autor:
Bagan, Guillaume
This thesis is dedicated to the evaluation of logical queries from the enumeration point of view. First, we deal with acyclic conjunctive formulas with inequalities; we show that such a query can be evaluated with linear delay in the size of the stru
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______166::a52cba1c33d29969e7f91473ae2e2be3
https://theses.hal.science/tel-00424232
https://theses.hal.science/tel-00424232
Autor:
Kanté, Mamadou Moustapha
Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière
Externí odkaz:
http://www.theses.fr/2008BOR13693/document
Autor:
Kanté, Mamadou Moustapha
Tous les problèmes définissables en \emph{logique monadique du second ordre } peuvent être résolus en temps polynomial dans les classes de graphes qui ont une \emph{largeur de clique} bornée. La largeur de clique est un paramètre de graphe déf
Externí odkaz:
http://tel.archives-ouvertes.fr/tel-00419301
http://tel.archives-ouvertes.fr/docs/00/41/93/01/PDF/KanteThesis2008E.pdf
http://tel.archives-ouvertes.fr/docs/00/41/93/01/PDF/KanteThesis2008E.pdf
Autor:
Lyaudet, Laurent
Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité imp
Externí odkaz:
http://tel.archives-ouvertes.fr/tel-00905137
http://tel.archives-ouvertes.fr/docs/00/90/51/37/PDF/these.pdf
http://tel.archives-ouvertes.fr/docs/00/90/51/37/PDF/these.pdf
Autor:
Lyaudet, Laurent
Beware, this abstract comports irony and humor. In this dissertation, we defend the idea that, for any reasonnable model of computation, this is not the model that is important to caracterize important complexity classes. Instead, what matters is the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______166::70ef3cd31f9e2a2afb175923f38edb2e
https://theses.hal.science/tel-00905137
https://theses.hal.science/tel-00905137