Gabow, Harold N.; Tarjan, Robert E. Efficient algorithms for a family of matroid intersection problems. (English) Zbl 0545.05029 J. Algorithms 5, 80-131 (1984). Assign real cost to each element of a matroid M and colour them by red or green; then find a minimal cost base having a given number of red elements. This is a matroid intersection problem where the second matroid has a very simple structure. Hence, instead of the usual algorithms which are polynomial but of high degree, the authors present much faster algorithms. Their implementation on specific matroids (if M is graphic transversal, matching ect.) shows that ”in all cases but one, the running time matches the best known algorithms for the problem without the red element constraint”. Reviewer: A.Recski Cited in 1 ReviewCited in 42 Documents MSC: 05B35 Combinatorial aspects of matroids and geometric lattices 68Q25 Analysis of algorithms and problem complexity Keywords:minimal cost base; matroid intersection problem PDFBibTeX XMLCite \textit{H. N. Gabow} and \textit{R. E. Tarjan}, J. Algorithms 5, 80--131 (1984; Zbl 0545.05029) Full Text: DOI