pith. sign in

arxiv: 1904.04129 · v1 · pith:3RFAXOXPnew · submitted 2019-04-08 · 💻 cs.DS

A note on Cunningham's algorithm for matroid intersection

classification 💻 cs.DS
keywords intersectionmatroidalgorithmcunninghamindependentmatroidsnotecalls
0
0 comments X
read the original 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(nr\log^2(r))$ independent oracle calls.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.