A note on Cunningham's algorithm for matroid intersection

2019/04/08 by Nguyen, Huy L.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1904.04129

Abstract

In the matroid intersection problem, we are given two matroids of rank r on a common ground set E of n elements and the goal is to find the maximum set that is independent in both matroids. In this note, we show that Cunningham's algorithm for matroid intersection can be implemented to use O(nrlog²(r)) independent oracle calls.

Related

• Matroid Intersection under Restricted Oracles
• Matroid Intersection under Restricted Oracles
• A Lower Bound for the Rank of Matroid Intersection
• Faster Matroid Intersection
• Matroid Intersection under Minimum Rank Oracle