论文标题
多项式的最小分离器的图形
Graphs with polynomially many minimal separators
论文作者
论文摘要
我们表明，不包含theta，金字塔，棱镜或乌龟作为诱导子图的图具有多个最小的分离器。从某种意义上说，如果排除了四个诱导子图中的三个，则该结果是最好的可能性。结果，有一种多项式时间算法来解决（theta，金字塔，棱镜，乌龟）类别的最大重量独立集问题。由于每个棱镜，theta和Turtle都包含一个均匀的孔，因此这也意味着一种多项式时间算法来解决（金字塔，甚至无孔）的最大重量独立集问题。
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.
