Listing all potential maximal cliques of a graph
Résumé
A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all graphs with polynomial number of minimal separators.
Une clique maximale potentielle d'un graphe est un ensemble de sommets qui induit une clique maximale dans au moins une triangulation minimale de ce graphe. Il a été prouvé que si ces objets peuvent être énumérés en temps polynomial pour une classe de graphes, la largeur arborescente et la complétion minimale sont calculables en temps polynomial pour ces graphes. Nous montrons ici que les cliques maximales potentielles d'un graphe peuvent être générées en temps polynomial par rapport au nombre de ses séparateurs minimaux. En conséquence, la largeur arborescente et la complétion minimale sont calculables en temps polynomial pour tous les graphes ayant un nombre polynomial de séparateurs minimaux.
Origine : Fichiers produits par l'(les) auteur(s)