Listing all potential maximal cliques of a graph - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1999

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.
Fichier principal
Vignette du fichier
RR1999-40.pdf (243.72 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102056 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102056 , version 1

Citer

Vincent Bouchitté, Ioan Todinca. Listing all potential maximal cliques of a graph. [Research Report] LIP RR-1999-40, Laboratoire de l'informatique du parallélisme. 1999, 2+13p. ⟨hal-02102056⟩
12 Consultations
241 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More