×

Efficient algorithms for a family of matroid intersection problems. (English) Zbl 0545.05029

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

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI