Listing all potential maximal cliques of a graph

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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102056
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:13:05 AM
Last modification on : Sunday, April 28, 2019 - 1:23:05 AM

File

RR1999-40.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102056, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

26