A weighted linear matroid parity algorithm
S Iwata, Y Kobayashi - Proceedings of the 49th Annual ACM SIGACT …, 2017 - dl.acm.org
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017•dl.acm.org
The matroid parity (or matroid matching) problem, introduced as a common generalization of
matching and matroid intersection problems, is so general that it requires an exponential
number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula
and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms
have been developed for the linear matroid parity problem. In this paper, we present a
combinatorial, deterministic, strongly polynomial algorithm for the weighted linear matroid …
matching and matroid intersection problems, is so general that it requires an exponential
number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula
and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms
have been developed for the linear matroid parity problem. In this paper, we present a
combinatorial, deterministic, strongly polynomial algorithm for the weighted linear matroid …
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.
In this paper, we present a combinatorial, deterministic, strongly polynomial algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach with the aid of the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果