期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 parity
sets) is in NC2, provided that there are polynomial bounded basic
matroid intersections (basic matroid parity sets). For the graphic
matroids, We show that constructing all basic matroid intersections
is in NC2 if the number of basic graphic matroid intersections is
polynomial bounded. To our knowledge, these algorithms are the first
deterministic NC-algorithms for matroid intersection and matroid
parity. Our result also answers a question of Harvey \cite{HAR}.
