Solving the linear matroid parity problem as a sequence of matroid intersection problems
Solving the linear matroid parity problem as a sequence of matroid intersection problems
复制标题
将线性拟阵奇偶校验问题求解为一系列拟阵相交问题
作者：
J. Orlin;J. V. Vate
在本文中，我们为线性矩阵奇偶校验问题提供了O（R4N）算法。 '可以作为Matroid相交问题解决的奇偶校验问题。在这个问题上，我们关注双重解决方案的一般结构特性，而不是在伴侣论文中的局部原始结构。
In this paper, we present an O(r4n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called ‘easy’ parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of ‘easy’ parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem.