Combinatorial optimization with 2-joins
Combinatorial optimization with 2-joins
复制标题
2-join 的组合优化
DOI：
10.1016/j.jctb.2011.06.002
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
Nicolas Trotignon;Kristina Vuskovic
2-连接是一种边割集，它自然出现在采用诱导子图封闭的几类图的分解中，例如完美图和无爪图。在本文中，我们构建了组合多项式时间算法，用于寻找可通过 2-连接分解的一类完美图的最大加权团、最大加权稳定集和最佳着色：完美图类没有平衡偏斜分区、补集中的 2-连接，也没有齐次对。我们开发的技术足够通用，可以轻松应用于为已知可通过 2-join 分解的另一类图（即没有星割集的偶孔无图类）找到最大加权稳定集。我们还给出了一类简单的图，可通过 2-join 分解为二部图和线图，并且找到最大稳定集是 NP 困难的。这表明，具有相同奇偶校验的孔为在计算稳定集合中使用 2-连接提供了基本属性。
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset. We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.
具有星割集和 2-连接的偶孔无图分解
DOI：
10.1016/j.jctb.2012.10.001
发表时间：
2013
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Da Silva M
通讯作者：
Da Silva M
更快地检测 2-join
DOI：
10.48550/arxiv.1107.3977
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Charbit P
通讯作者：
Charbit P