Random pseudo-polynomial algorithms for exact matroid problems. (English) Zbl 0773.05032

Authors’ abstract: In this work we present a random pseudo-polynomial algorithm for the problem of finding a base of specified value in a weighted represented matroid, subject to parity conditions. We also describe a specialized version of the algorithm suitable for finding a base of specified value in the intersection of two matroids. This result generalizes an existing pseudo-polynomial algorithm for computing exact arborescences in weighted graphs. Another (simpler) specialized version of our algorithms is also presented for computing perfect matchings of specified value in weighted graphs.
Reviewer: J.Libicher (Brno)


05B35 Combinatorial aspects of matroids and geometric lattices
68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68W10 Parallel algorithms in computer science
Full Text: DOI Link