Name
Abstract | ||
|---|---|---|
We use the notion of potential maximal clique to characterize the maximal cliques appearing in minimal triangulations of a graph. We show 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 prove that for all classes of graphs for which polynomial algorithms computing the treewidth and the minimum fill-in exist, we can list their potential maximal cliques in polynomial time. Our approach unifies these algorithms. Finally we show how to compute in polynomial time the potential maximal cliques of weakly triangulated graphs for which the treewidth and the minimum fill-in problems were open. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S0097539799359683 | SIAM J. Comput. |
Keywords | Field | DocType |
minimum fill-in,potential maximal clique,polynomially tractable,minimum fill-in problem,polynomial time,minimal triangulations,minimal separators,maximal clique,polynomial algorithm,weakly triangulated graph,treewidth | Discrete mathematics,Combinatorics,Tree-depth,Partial k-tree,K-tree,Clique-sum,Chordal graph,Treewidth,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 0097-5397 |
Citations | PageRank | References |
54 | 2.23 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Bouchitté | 1 | 172 | 12.07 |
| Ioan Todinca | 2 | 328 | 27.33 |