论文标题
一种简单的组合算法，用于亚皮图中的2个匹配限制 - 通过半边缘
A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
论文作者
论文摘要
我们考虑了三个变体的问题，即在亚立方图$ g $中找到最大权重限制$ 2 $。 （$ 2 $匹配是边缘的任何子集，使每个顶点最多都发生在其边缘中的最多两个。）具体取决于限制的$ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ 2 $ - 无三角形或无方形或三角形和无三角形和无形的和平方。虽然对于前两种$ 2 $匹配的前两种类型的多项式时间算法，但它们非常复杂或使用高级方法。对于这三个问题，我们将简单地减少了最大重量$ b $匹配的计算。借助半边缘进行还原。从非正式的话来说，Edge $ e $的半边缘是$ e $的一半，其中恰好包含其终点之一。对于$ g $的三角形的子集，我们用两个半边替换了这样的三角形的每个边缘。一个边缘的两个半边缘$ w（e）$可能会获得不同的权重，不一定等于$ \ frac {1} {2} {2} w（e）$。在指标设置中，当边缘重量满足三角形不等式时，这具有几何解释，该解释与circtle隔离三角形边缘的边缘如何相关。我们的算法又比以前已知的要快。它们每个的运行时间为$ O（n^2 \ log {n}）$，其中$ n $表示图中的顶点数。
We consider three variants of the problem of finding a maximum weight restricted $2$-matching in a subcubic graph $G$. (A $2$-matching is any subset of the edges such that each vertex is incident to at most two of its edges.) Depending on the variant a restricted $2$-matching means a $2$-matching that is either triangle-free or square-free or both triangle- and square-free. While there exist polynomial time algorithms for the first two types of $2$-matchings, they are quite complicated or use advanced methodology. For each of the three problems we present a simple reduction to the computation of a maximum weight $b$-matching. The reduction is conducted with the aid of half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints. For a subset of triangles of $G$, we replace each edge of such a triangle with two half-edges. Two half-edges of one edge $e$ of weight $w(e)$ may get different weights, not necessarily equal to $\frac{1}{2}w(e)$. In the metric setting when the edge weights satisfy the triangle inequality, this has a geometric interpretation connected to how an incircle partitions the edges of a triangle. Our algorithms are additionally faster than those known before. The running time of each of them is $O(n^2\log{n})$, where $n$ denotes the number of vertices in the graph.
