Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems
Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems
复制标题
线性拟阵相交问题的高效理论与实践算法
DOI：
10.1006/jcss.1996.0054
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Ying Xu
中科院分区：
文献类型：
--
作者：
H. Gabow;Ying Xu
有效的算法的拟阵相交问题，基数和加权版本，提出。加权求交的算法是通过调整权值来实现的。基数算法是一个特例，但它利用了更大的结构。线性拟阵上的几个实现的算法的效率说明。考虑一个m元秩n的线性拟阵。假设所有元素的权重都是大小不超过N的整数。我们最快的算法使用时间O（mn1.77log（nN））和O（mn1.62）分别为加权和未加权的交集，这提高了以前的最佳界限，O（mn2.4）和O（mn2logn），分别。对拟阵交在数值计算和动力系统中的几个应用作了相应的改进。
Efficient algorithms for the matroid intersection problem, both cardinality and weighted versions, are presented. The algorithm for weighted intersection works by scaling the weights. The cardinality algorithm is a special case, but takes advantage of greater structure. Efficiency of the algorithms is illustrated by several implementations on linear matroids. Consider a linear matroid withmelements and rankn. Assume all element weights are integers of magnitude at mostN. Our fastest algorithms use timeO(mn1.77log(nN)) andO(mn1.62) for weighted and unweighted intersection, respectively; this improves the previous best bounds,O(mn2.4) andO(mn2logn), respectively. Corresponding improvements are given for several applications of matroid intersection to numerical computation and dynamic systems.