Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Reachability
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook
,
Yonggang Jiang
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
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
×