An algorithm for packing non-zero A-paths in group-labelled graphs
An algorithm for packing non-zero A-paths in group-labelled graphs
复制标题
DOI：
10.1007/s00493-008-2157-8
复制
发表时间：
2008-01-01
期刊：
影响因子：
1.1
通讯作者：
Geelen, Jim
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Cunningham, William H.;Geelen, Jim
设G =（V，E）是一个有向图，其边由群Gamma的元素标号，设A是V的子集。A-路是两端都在A中的路。路径P在G中的权重是向前定向的弧上的群值之和减去P中向后定向的弧的和。（如果Gamma不是阿贝尔的，我们将标签按它们沿路径的顺序沿着求和。）本文给出了一个求顶点不相交的非零权A-路的最大集合的有效算法。当A=V时，这个问题等价于最大匹配问题。
Let G = (V, E) be an oriented graph whose edges are labelled by the elements of a group Gamma and let A subset of V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Gamma is not abelian, we sum the labels in their order along the path.) We give an efficient algorithm for finding a maximum collection of vertex-disjoint A-paths each of non-zero weight. When A=V this problem is equivalent to the maximum matching problem.