BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-73-342
       ENTRY:: September 25, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Matroid partitioning.
        TYPE:: Technical Report
      AUTHOR:: Knuth, Donald E.
        DATE:: March 1973
       PAGES:: 13
    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.
       NOTES:: [Adminitrivia V1/Prg/19950925]
         END:: STAN//CS-TR-73-342