ALGEBRAIC ALGORITHMS FOR MATCHING AND MATROID PROBLEMS
ALGEBRAIC ALGORITHMS FOR MATCHING AND MATROID PROBLEMS
复制标题
DOI：
10.1137/070684008
复制
发表时间：
2009-01-01
影响因子：
1.6
通讯作者：
Harvey, Nicholas J. A.
中科院分区：
文献类型：
--
作者：
Harvey, Nicholas J. A.
我们为两个众所周知的组合问题提出了新的代数方法：非面积匹配和Matroid相交。我们的工作产生了超过或匹配现有算法效率的新的随机算法。对于非分数匹配，我们获得了一种简单的，纯粹的代数算法，其运行时间o（n（omega）），其中n是顶点的数量，而欧米茄是矩阵乘法指数。这解决了Mucha和Sankowski（2004）的中心开放问题。对于Matroid相交，我们的算法具有n个元素和秩R的矩形且满足某些自然条件的rangroids的运行时间O（NR（Omega-1））。
We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n(omega)) where n is the number of vertices and omega is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr(omega-1)) for matroids with n elements and rank r that satisfy some natural conditions.