A fast algorithm to construct a representation for transversal matroids

作者：Rekab Eslami Morteza^*; Esmaeili Morteza; Gulliver T Aaron

来源：Japan Journal of Industrial and Applied Mathematics, 2016, 33(1): 207-226.

DOI：10.1007/s13160-016-0209-9

• Transversal matroids
• Representation matrix
• Complete matching

Transversal matroids were introduced in the mid 1960s and unified many results in transversal theory. Piff and Welsh proved that a transversal matroid is representable over all sufficiently large fields. To date, their merge algorithm is the only known algorithm to construct a representation matrix for a given transversal matroid. In this paper, a new algorithm to construct a representation matrix for a given transversal matroid is proposed that is faster than the Piff-Welsh algorithm. Let G = (V-(1)(U) over dotV(2), E) be the bipartite graph representing a transversal matroid and M the set of all complete matchings of G. The time complexity of the proposed algorithm is O(vertical bar V-(1)vertical bar(1/2)vertical bar E vertical bar + vertical bar V-(1)parallel to M vertical bar). This algorithm makes use of complete matchings of bipartite graphs instead of matrix determinants, and an enumeration algorithm is used to find these matchings.

• 出版日期2016-2