Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Matroid Intersection:
TR12-066 | 22nd April 2012
Jinyu Huang

Parallel Complexity for Matroid Intersection and Matroid Parity Problems

Revisions: 1

Let two linear matroids have the same rank in matroid intersection.
A maximum linear matroid intersection (maximum linear matroid parity
set) is called a basic matroid intersection (basic matroid parity
set), if its size is the rank of the matroid. We present that
enumerating all basic matroid intersections (basic matroid ... more >>>

TR16-182 | 14th November 2016
Rohit Gurjar, Thomas Thierauf

Linear Matroid Intersection is in quasi-NC

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

TR21-121 | 21st August 2021
Sumanta Ghosh, Rohit Gurjar

Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision

We study the matroid intersection problem from the parallel complexity perspective. Given
two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted ... more >>>

ISSN 1433-8092 | Imprint