Lecture Notes in Computer Science, 2000, Volume 1770/2000, 503-515, DOI: 10.1007/3-540-46541-3_42

Listing All Potential Maximal Cliques of a Graph

Vincent Bouchitté and Ioan Todinca

View Related Documents

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

Fulltext Preview

Image of the first page of the fulltext document