Algorithmique combinatoire : cliques, bicliques et systèmes implicatifs / Alain Gély ; sous la direction de Nourine Lhouari

Date :

Editeur / Publisher : [S. l.] : [s. n.] , 2005

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Analyse combinatoire énumérative

Théorie des graphes

Nourine, Lhouari (Directeur de thèse / thesis advisor)

Université Blaise Pascal (Clermont-Ferrand ; 1976-2016) (Organisme de soutenance / degree-grantor)

Relation : Algorithmique combinatoire : cliques, bicliques et systèmes implicatifs / Alain Gély ; sous la direction de Nourine Lhouari / Grenoble : Atelier national de reproduction des thèses , 2005

Résumé / Abstract : Cette thèse traite de l'algorithmique d'énumération. Après avoir présenté les concepts particuliers des algorithmes d'énumération, nous nous intéressons plus particuliérement à deux problèmes, l'énumération des cliques maximales et l'énumération des bicliques maximales d'un graphe. Pour ce dernier problème, trois variantes seront traitées : énumération des bicliques maximales induites, non induites et pour le cas particulier des graphes biparti. Cette thèse propose des liens entre les algorithmes existants pour ces problèmes. On s'intéresse à l'énumération des éléments d'une base minimun d'implications. Comme il n'existe pas à l'heure actuelle d'algorithme d'énumération polynomial pour ce problème, les approches présentées ici utilisent un autre angle d'approche : trouver une base minimun plus petite, ou plus rapide à calculer, permettant de reconstruire la base minimum initiale en temps polynomial. Dans ce but, deux résultats sont présentés : les éléments clones d'une relation et la famille des systèmes de fermeture partageant une certaine partie d'une base minimun