Name
Abstract | ||
|---|---|---|
We give a characterization of minimal triangulation of graphs using the notion of "maximal set of neighbor separators". We prove that if all the maximal sets of neighbor separators of some graphs can be computed in polynomial time, the treewidth of those graphs can be computed in polynomial time. This notion also unifies the already known algorithms computing the treewidth of several classes of graphs. |
Year | Venue | Keywords |
|---|---|---|
1998 | ESA | maximal set,neighbor separator,polynomial time,minimal triangulations,minimal separators,minimal triangulation,chordal graph |
Field | DocType | ISBN |
Discrete mathematics,Combinatorics,Indifference graph,Partial k-tree,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics,Maximal independent set | Conference | 3-540-64848-8 |
Citations | PageRank | References |
5 | 0.63 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Bouchitté | 1 | 172 | 12.07 |
| Ioan Todinca | 2 | 328 | 27.33 |