{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T13:40:18Z","timestamp":1682602818057},"reference-count":26,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1051\/ita:2000108","type":"journal-article","created":{"date-parts":[[2003,11,14]],"date-time":"2003-11-14T15:08:26Z","timestamp":1068822506000},"page":"87-97","source":"Crossref","is-referenced-by-count":0,"title":["Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases"],"prefix":"10.1051","volume":"34","author":[{"given":"E.","family":"Bampis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Giannakos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Karzanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Manoussakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Milis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2002,4,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(91)90195-N","volume":"37","author":"Alt","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"R2","unstructured":"E. Bampis, A. Giannakos, A. Karzanov, I. Milis and Y. Manoussakis,Matchings in cubic graphs are as difficult as in general graphs, Rapport de Recherche No. 12. LaMI, Universit\u00e9 d' Evry - Val d'Essonne (1995)."},{"key":"R3","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"R4","first-page":"203","volume":"4","author":"Chiba","year":"1981","journal-title":"J. Inform. Process."},{"key":"R5","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/0022-0000(92)90005-4","volume":"44","author":"Dahlhaus","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"R6","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"Edmonds","year":"1965","journal-title":"Canad. J. Math."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"T. Feder and R. Motwani,Clique partitions, graph compression and speeding-up algorithms, $23^{\\rm th}$ STOC (1991) 123-133.","DOI":"10.1145\/103418.103424"},{"key":"R8","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jagm.1993.1009","volume":"14","author":"Goldberg","year":"1993","journal-title":"J. Algorithms"},{"key":"R9","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1145\/234782.234783","volume":"27","author":"Greenlaw","year":"1995","journal-title":"ACM Computing Surveys"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D.Yu. Grigoriev and M. Karpinski,The matching problem for bipartite graphs with polynomially bounded permanents is in NC, $28^{\\rm th}$ FOCS (1987) 166-172.","DOI":"10.1109\/SFCS.1987.56"},{"key":"R11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0890-5401(90)90034-F","volume":"84","author":"Hagerup","year":"1990","journal-title":"Inform. and Comput."},{"key":"R12","unstructured":"M. Karpinski and W. Rytter,Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear)."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"G. Lev, N. Pippenger and L. Valiant, A fast parallel algorithm for routing in permutation networks.IEEE Trans. Comput.C-30(1981) 93-100.","DOI":"10.1109\/TC.1981.6312171"},{"key":"R14","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(93)90117-R","volume":"35","author":"Liang","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"R15","unstructured":"L. Lovasz and M. Plummer,Matching Theory. Elsevier Science Publishers (1986)."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Micali and V.V. Vazirani,An$O(\\vert V\\vert^{\\frac {1}{2}}\\vert E\\vert)$algorithm for finding maximum matchings in general graphs, $21^{\\rm th}$ FOCS (1980) 17-23.","DOI":"10.1109\/SFCS.1980.12"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"G.L. Miller and J. Naor,Flow in planar graphs with multiply sources and sinks, Proc. $30^{\\rm th}$ FOCS (1989) 112-117.","DOI":"10.1109\/SFCS.1989.63464"},{"key":"R18","unstructured":"A. Moitra and R. Jonhson,Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988)."},{"key":"R19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"Mulmuley","year":"1987","journal-title":"Combinatorica"},{"key":"R20","unstructured":"T. Nishizeki and N. Chiba,Planar Graphs: Theory and Algorithms. North-Holland (1988)."},{"key":"R21","unstructured":"O. Ore,The four color problem. Academic Press, New York (1967)."},{"key":"R22","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0167-5060(08)70395-9","volume":"55","author":"Plummer","year":"1993","journal-title":"Ann. Discrete Math."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"S.V. Ramachandran and J.H. Reif,An optimal parallel algorithm for graph planarity, $30^{\\rm th}$ FOCS (1989) 282-287.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"R24","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"Rabin","year":"1989","journal-title":"J. Algorithms"},{"key":"R25","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"Vazirani","year":"1989","journal-title":"Inform. and Comput."},{"key":"R26","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"Vazirani","year":"1994","journal-title":"Combinatorica"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2000108\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T13:17:23Z","timestamp":1682601443000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2000108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":26,"journal-issue":{"issue":"2"},"alternative-id":["ita0009"],"URL":"https:\/\/doi.org\/10.1051\/ita:2000108","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}