Given a bipartite graph G = (U ∪+ V, E), a linear representation of the transversal matroid associated with G on the ground set U, can be constructed in randomized polynomial time. In fact one can get a linear representation deterministically in time 2~(O(m~2n)), where m = |U| and n = |V|, by looping through all the choices made in the randomized algorithm. Other important matroids for which one can obtain linear representation deterministically in time similar to the one for transversal matroids include gammoids and strict gammoids. Strict gammoids are duals of transversal matroids and gammoids are restrictions of strict gammoids. We give faster deterministic algorithms to construct linear representations of transversal matroids, gammoids and strict gammoids. All our algorithms run in time (_r~m)m~(o(1)), where m is the cardinality of the ground set and r is the rank of the matroid. In the language of parameterized complexity, we give an XP algorithm for finding linear representations of transversal matroids, gammoids and strict gammoids parameterized by the rank of the given matroid.
展开▼
机译：给定二部图G =（U + V，E），则可以在随机多项式时间内构造与地面集合U上的G相关的横向拟阵的线性表示。实际上，可以在时间2〜（O（m〜2n））中确定性地获得线性表示，其中m = | U | n = | V |，通过遍历随机算法中的所有选择。其他重要的类人动物可以在时间上确定性地获得线性表示，类似于横向类人动物，包括gammoids和strict gammoids。严格的gammaoids是横向拟阵的对偶，gammaoids是严格的gammaoid的限制。我们给出了更快的确定性算法，以构造横向拟阵，类伽马和严格类伽马的线性表示。我们所有的算法都按时间（_r〜m）m〜（o（1））运行，其中m是地面集合的基数，r是拟阵的秩。用参数化复杂度的语言，我们提供了一种XP算法，用于查找由给定拟阵的等级参数化的横向拟阵，类伽马和严格类伽马的线性表示形式。
展开▼
