Listing all potential maximal cliques of a graph

https://doi.org/10.1016/S0304-3975(01)00007-XGet rights and content
Under an Elsevier user license
open archive

Abstract

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 classes of graphs with a polynomial number of minimal separators.

Keywords

Graph algorithms
Treewidth
Minimal separators
Potential maximal cliques

Cited by (0)