Matroid partitioning.
Matroid partitioning.
复制标题
拟阵划分。
DOI：
--
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
D. Knuth
中科院分区：
文献类型：
--
作者：
D. Knuth
本文讨论了Edmonds算法的一个改进版本，用于在各种给定的拟阵中将集合划分为独立的子集。如果${cal M}_1$，…，${cal M}_k$是定义在有限集合E上的矩阵，该算法给出了一个简单的充要条件，即E的元素是否可以用k种颜色着色，使得(i)颜色j的所有元素在${cal M}_j$中是独立的，（ii）颜色j的元素个数在给定的极限$n_j leq | E_j | leq {n'}_j$之间。在对给定的矩阵（其中n是E中元素的个数）进行最多$n^3$ + $n^2$k次的独立性测试后，算法要么找到这样的着色，要么找到不存在的证明。
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.