Efficient Theoretic and Practical Algorithms for Linear Matroid Intersection Problems

✍ Scribed by Harold N. Gabow; Ying Xu

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 754 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0054

✦ Synopsis

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 with m elements and rank n. Assume all element weights are integers of magnitude at most N. Our fastest algorithms use time O(mn 1.77 log(nN)) and O(mn 1.62 ) for weighted and unweighted intersection, respectively; this improves the previous best bounds, O(mn 2.4 ) and O(mn 2 log n), respectively. Corresponding improvements are given for several applications of matroid intersection to numerical computation and dynamic systems.