论文标题
在适当的间隔图和相关图类中的最大基数切割问题上
On the Maximum Cardinality Cut Problem in Proper Interval Graphs and Related Graph Classes
论文作者
论文摘要
尽管在两篇不同的论文中宣称，最大的基数切割问题是可溶解的多项式时间，可用于适当的间隔图，但两者都是错误的。在本文中，我们在包含适当的间隔图和混合单位间隔图的类别的最大基数切割问题中给出了FPT算法，当时我们引入了一些新参数。这些新参数与适当的间隔图和混合单位间隔图的所谓气泡表示以及集团宽度分解有关。
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this paper, we give FPT algorithms for the maximum cardinality cut problem in classes of graphs containing proper interval graphs and mixed unit interval graphs when parameterized by some new parameters that we introduce. These new parameters are related to a generalization of the so-called bubble representations of proper interval graphs and mixed unit interval graphs and to clique-width decompositions.
