Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Matroid intersection
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad
,
Danupon Nanongkai
,
Ta-Wei Tu
,
Sagnik Mukhopadhyay
Breaking the Quadratic Barrier for Matroid Intersection
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids ${\cal M}_1 = (V, {\cal I}_1)$ and ${\cal M}_2 = (V, {\cal I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S \in {\cal I}_1 \cap {\cal I}_2$ by making independence oracle queries of the form ‘‘Is $S \in {\cal I}_1$?
Joakim Blikstad
,
Jan van den Brand
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
Cite
×