Paper Info
Title
An Augmenting Path Algorithm For The Parity Problem On Linear Matroids
Abstract
The matroid parity problem is a generalization of matroid intersection and general graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm for linear matroids was presented by Lovasz. This paper presents an algorithm that uses time 0(mn/sup 3/), where m is the number of elements and n is the rank; for the spanning tree parity problem the time 0(mn/sup 2/). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.
Year
DOI
Venue
1984
10.1109/SFCS.1984.715918
FOCS
Keywords
Field
DocType
graphics,computer science,scheduling algorithm,tree graphs,network flow,spanning tree,polynomials,graph matching
Matroid,Discrete mathematics,Combinatorics,Dinic's algorithm,Matroid intersection,Algorithm,Matroid partitioning,Graphic matroid,Spanning tree,Circuit rank,Mathematics,Branch-decomposition
Conference
ISSN
ISBN
Citations 
0272-5428
0-8186-0591-X
7
PageRank 
References 
Authors
0.81
7
2
Name
Order
Citations
PageRank
Matthias F. M. Stallmann116619.38
Harold N. Gabow23753691.41