The Weighted Independent Even Factor Algorithm
The Weighted Independent Even Factor Algorithm
复制标题
加权独立偶数因子算法
DOI：
10.1007/s10107-010-0397-z
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Takazawa
中科院分区：
文献类型：
--
作者：
Y. Asahiro;J. Jansson;E. Miyano;H. Ono;K. Takazawa
偶因子是偶长有向圈和有向路的顶点不相交的集合。一个偶因子被称为独立的，如果它满足一定的拟阵约束。寻找一个最大尺寸的独立偶因子的问题是非二部匹配和拟阵交问题的一个常见推广。本文给出了奇圈对称加权有向图的加权独立偶因子问题的一个原-对偶算法。Cunningham和Geelen证明了这个问题可以通过赋值拟阵交来解决。他们的方法产生了一个运行时间为O（n3γ+ n6 m）的组合算法，其中和分别是顶点和边的数量，γ是独立性测试的时间。相比之下，将加权偶因子算法和独立偶因子算法相结合，我们的算法更直接，运行时间为O（n4γ+n5）。该算法是完全组合的，从而提供了一个新的对偶积分定理，一般推广的匹配和拟阵交的全对偶积分定理。
An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n3γ+n6m) time, wherenandmare the number of vertices and edges, respectively, andγis the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n4γ+n5) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.