文章基本信息

标题：Parallel Complexity for Matroid Intersection and Matroid Parity Problems
本地全文：下载
作者：Jinyu Huang
期刊名称：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}.
关键词：Matroid Intersection, Matroid Parity, NC Algorithms