{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T23:58:43Z","timestamp":1648684723609},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> A maximum linear matroid parity set is called a basic matroid parity set, if its size is the rank of the matroid. We show that determining the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity) is in NC<jats:sup>2<\/jats:sup>, provided that there are polynomial number of common bases (basic matroid parity sets). For graphic matroids, we show that finding a common base for matroid intersection is in NC<jats:sup>2<\/jats:sup>, if the number of common bases is polynomial bounded. To our knowledge, these algorithms are the first deterministic NC algorithms for matroid intersection and matroid parity. We also give a new RNC<jats:sup>2<\/jats:sup> algorithm that finds a common base for graphic matroid intersection. We prove that if there is a black-box NC algorithm for Polynomial Identity Testing (PIT), then there is an NC algorithm to determine the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity). <\/jats:p>","DOI":"10.1142\/s1793830915500196","type":"journal-article","created":{"date-parts":[[2015,3,23]],"date-time":"2015-03-23T01:43:24Z","timestamp":1427075004000},"page":"1550019","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for matroid intersection and matroid parity"],"prefix":"10.1142","volume":"07","author":[{"given":"Jinyu","family":"Huang","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Illinois Institute of Technology, Engineering 1 Building 10 West 32nd Street, Chicago, IL, 60616, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,5,25]]},"reference":[{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001119"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0013-7"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"rf13","series-title":"Algorithms and Complexity: Vol. A","volume-title":"Handbook of Theoretical Computer Science","author":"Karp R. M.","year":"1994"},{"key":"rf14","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming","volume":"1","author":"Knuth D. E.","year":"1997"},{"key":"rf15","volume-title":"Matching Theory","author":"Lov\u00e4sz L.","year":"1986"},{"key":"rf20","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"rf21","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90017-5"},{"key":"rf23","volume-title":"Matroid Theory","author":"Welsh D. J. A.","year":"1976"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830915500196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:36:12Z","timestamp":1565148972000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830915500196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,25]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,5,25]]},"published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1142\/S1793830915500196"],"URL":"https:\/\/doi.org\/10.1142\/s1793830915500196","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,25]]}}}