An augmenting path algorithm for linear matroid parity

An augmenting path algorithm for linear matroid parity
复制标题

线性拟阵奇偶校验的增广路径算法

DOI：
--
复制
发表时间：
1986
期刊：
Comb.
影响因子：
--
通讯作者：
Matthias F. Stallmann
Matthias F. Stallmann
中科院分区：
--
文献类型：
--
作者：
H. Gabow;Matthias F. Stallmann

文献摘要

被引文献

相似文献

线性拟阵奇偶性推广了拟阵交和图匹配（以及网络流、度约束子图等）。一个多项式算法由Lovász给出。本文提出了一个算法，使用时间O（mn 3），其中m是元素的数量和n是秩。(The使用快速矩阵乘法，时间为O（mn2.5）;两个界限都假设统一成本模型）。对于图拟阵，时间是O（mn ~ 2）。该算法的基础上增加路径的方法中使用的算法的所有子情况的问题。
Linear matroid parity generalizes matroid intersection and graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm was given by Lovász. This paper presents an algorithm that uses timeO(mn3), wherem is the number of elements andn is the rank. (The time isO(mn2.5) using fast matrix multiplication; both bounds assume the uniform cost model). For graphic matroids the time isO(mn2). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.