Strict matching matroids and matroid algorithms

A simple characterization of the set MCOLOOP of coloops in the strict matching matroid of an undirected graph G - (V,n) is provided, which allows the Edmonds decomposition of G to be produced in O(|V|5/2) Based on this decomposition, we have the following results' Two graphs associated with G are produced in . One is a bipartite graph with at most edges whose transversal matroid is isomorphic to the strict matching matroid of G; the other is a directed graph with at most edges, represending the strict gammoid dual to the strict matching matroid. The matroid components of the strict matching matroid of G are produced in , where ∂ is the matching defect of G and K(G) number of component G(V MCOLOOP). We show how to list the bases of the strict matching matroid of G and also calculate its Whitney and Tutle polynomials, in where N is the number of bases in the matroid.