{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:17:35Z","timestamp":1764587855984,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,27]],"date-time":"2017-04-27T00:00:00Z","timestamp":1493251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["TH 472\/4"],"award-info":[{"award-number":["TH 472\/4"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            A\n            <jats:italic>red-blue graph<\/jats:italic>\n            is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect matching problem. Hence, an efficient parallel algorithm for perfect matching would carry over to the exact perfect matching problem for this class of graphs. We also report some progress in extending the result to arbitrary graphs.\n          <\/jats:p>","DOI":"10.1145\/3041402","type":"journal-article","created":{"date-parts":[[2017,4,28]],"date-time":"2017-04-28T12:38:23Z","timestamp":1493383103000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Exact Perfect Matching in Complete Graphs"],"prefix":"10.1145","volume":"9","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Korwar","sequence":"additional","affiliation":[{"name":"Paris Diderot University, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"Messner","sequence":"additional","affiliation":[{"name":"Aalen University, Aalen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[{"name":"Aalen University, Aalen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,4,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_2_1","volume-title":"Technical Report QP-2011-02. Egerv\u00e1ry","author":"Geerdes H.-F.","year":"2011","unstructured":"H.-F. Geerdes and J. Szab\u00f3 . 2011 . A Unified Proof for Karzanov\u2019s Exact Matching Theorem . Technical Report QP-2011-02. Egerv\u00e1ry Research Group , Budapest, Hungary . http:\/\/bolyai.cs.elte.hu\/egres\/. H.-F. Geerdes and J. Szab\u00f3. 2011. A Unified Proof for Karzanov\u2019s Exact Matching Theorem. Technical Report QP-2011-02. Egerv\u00e1ry Research Group, Budapest, Hungary. http:\/\/bolyai.cs.elte.hu\/egres\/."},{"key":"e_1_2_1_3_1","volume-title":"Technical Report TR11-148. Electronic Colloquium on Computational Complexity (ECCC)","author":"Gurjar R.","year":"2011","unstructured":"R. Gurjar , A. Korwar , J. Messner , S. Straub , and T. Thierauf . 2011 . Planarizing Gadgets for Perfect Matching Do Not Exist. Technical Report TR11-148. Electronic Colloquium on Computational Complexity (ECCC) , Potsdam, Germany . (Revised version appears in proceedings of MFCS 2012.) R. Gurjar, A. Korwar, J. Messner, S. Straub, and T. Thierauf. 2011. Planarizing Gadgets for Perfect Matching Do Not Exist. Technical Report TR11-148. Electronic Colloquium on Computational Complexity (ECCC), Potsdam, Germany. (Revised version appears in proceedings of MFCS 2012.)"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01068796"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322309"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00300-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9519-0"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3041402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3041402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:52Z","timestamp":1750220632000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3041402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,27]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3041402"],"URL":"https:\/\/doi.org\/10.1145\/3041402","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2017,4,27]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}