论文标题
细长的树木切宽
Slim Tree-Cut Width
论文作者
论文摘要
树切宽是一个参数，它已被引入，以获取用于边缘切割的树宽的类似物。不幸的是，尽管它具有理想的结构特性，但事实证明，树切宽的宽度短于算法方面的基于边缘的基于边缘的替代品。这导致最近引入了一个简单的基于边缘的参数，称为边缘宽度[WG 2022]，该参数完全具有算法应用程序，人们会期望从树宽的类似物中进行边缘切割，但没有所需的结构属性。在本文中，我们研究了通过更改树木切分解中所谓的薄节点的阈值从2到1所获得的变种。我们表明，这种“细长的树木切宽度”满足了基于边缘的基于边缘的类似物的所有要求，结构和algorithmic和algorithmic and condectial and Crestical and Cristical bel and Edge bic cut-cut bedcut bactimitive bed bedcut bactimential with。我们的结果还包括通过易于使用的跨越树的分解，类似于用于边缘切割宽度的较小树木的宽度宽度的替代表征，以禁止的沉浸式以及用于计算参数的近似算法的表征。
Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as approximation algorithm for computing the parameter.
