Report Number: CS-TR-73-342
Institution: Stanford University, Department of Computer Science
Title: Matroid partitioning.
Author: Knuth, Donald E.
Date: March 1973
Abstract: This report discusses a modified version of Edmonds's algorithm for partitioning of a set into subsets independent in various given matroids. If ${\cal M}_1$,...,${\cal M}_k$ are matroids defined on a finite set E, the algorithm yields a simple necessary and sufficient condition for whether or not the elements of E can be colored with k colors such that (i) all elements of color j are independent in ${\cal M}_j$, and (ii) the number of elements of color j lies between given limits, $n_j \leq \| E_j \| \leq {n'}_j$. The algorithm either finds such a coloring or it finds a proof that none exists, after making at most $n^3$ + $n^2$k tests of independence in the given matroids, where n is the number of elements in E.