Paper Info
Title
An augmenting path algorithm for linear matroid parity
Abstract
Linear matroid parity generalizes matroid intersection and graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm was given by Lovsz. This paper presents an algorithm that uses timeO(mn 3), wherem is the number of elements andn is the rank. (The time isO(mn 2.5) using fast matrix multiplication; both bounds assume the uniform cost model). For graphic matroids the time isO(mn 2). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.
Year
DOI
Venue
1986
10.1007/BF02579169
Combinatorica
Keywords
Field
DocType
linear matroid parity,augmenting path algorithm,graph matching,network flow,matrix multiplication
Matroid,Discrete mathematics,Combinatorics,Matroid intersection,Oriented matroid,Algorithm,Matching (graph theory),Matroid partitioning,Graphic matroid,Weighted matroid,Matrix multiplication,Mathematics
Journal
Volume
Issue
ISSN
6
2
1439-6912
Citations 
PageRank 
References 
31
2.79
11
Authors
2
Name
Order
Citations
PageRank
Harold N. Gabow13753691.41
Matthias F. M. Stallmann216619.38