Graphs with polynomially many minimal separators
Graphs with polynomially many minimal separators
复制标题
具有多项式多个最小分隔符的图
DOI：
10.1016/j.jctb.2021.10.003
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vušković, Kristina
中科院分区：
文献类型：
--
作者：
Abrishami, Tara;Chudnovsky, Maria;Dibek, Cemil;Thomassé, Stéphan;Trotignon, Nicolas;Vušković, Kristina
我们证明，不包含 theta、金字塔、棱柱或海龟作为导出子图的图具有多项式许多最小分隔符。如果仅排除四个导出子图中的三个，则存在具有指数数量的最小分隔符的图，从这个意义上来说，该结果是最好的。因此，存在一种多项式时间算法来解决无（theta、金字塔、棱镜、海龟）类图的最大权独立集问题。由于每个棱柱、theta 和海龟都包含一个偶数孔，这也意味着使用多项式时间算法来解决无（金字塔、偶数孔）类图的最大权重独立集问题。
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.
登录
查看更多内容
Jul l 2 01 7 关于（菱形，偶孔）无图的等级宽度
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Isolde Adler;N. Le;H. Müller;M. Radovanović;Nicolas Trotignon;Kristina Vuskovic
通讯作者：
Kristina Vuskovic
无P6图上最大权独立集的多项式时间算法
DOI：
10.1137/1.9781611975482.77
发表时间：
2017
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Andrzej Grzesik;Tereza Klimošová;Marcin Pilipczuk;Michal Pilipczuk
通讯作者：
Michal Pilipczuk
DOI：
10.1137/1.9781611976465.116
发表时间：
2020
期刊：
ArXiv
影响因子：
--
作者：
Tara Abrishami;M. Chudnovsky;Marcin Pilipczuk;Paweł Rzaͅżewski;P. Seymour
通讯作者：
P. Seymour
无（金字塔、偶孔）图中的最大独立集
DOI：
--
发表时间：
2019
期刊：
arXiv.org
影响因子：
--
作者：
M. Chudnovsky;Stéphan Thomassé;Nicolas Trotignon;Kristina Vuskovic
通讯作者：
Kristina Vuskovic