2026-08-17T17:37:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8273 2024-03-06T10:41:45Z ddc:004 open_access

Weighted Linear Matroid Parity Iwata, Satoru Matroid matching Pfaffian polynomial-time algorithm 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. Nevertheless, Lovasz (1978) 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. This talk presents a recently developed polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satoru Iwata 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.1 urn:nbn:de:0030-drops-82738 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.1 eng https://creativecommons.org/licenses/by/3.0/legalcode