{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T17:47:03Z","timestamp":1648576023706},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1998,9]]},"abstract":"<jats:p> We present au intuitive and simple O( log <jats:sup>2<\/jats:sup> n log \u03a6) time, O(n<jats:sup>2<\/jats:sup> M(n)) processor parallel algorithm for finding a perfect matching in a planar graph, where n is the order, \u03a6 is the number of the distinct perfect matchings of the graph and M(n) is the best sequential complexity of matrix multiplication of size n. The algorithm runs on a CRCW PRAM. Clearly, our algorithm belongs to the class NC if the number of perfect matchings is polynomially bounded in the size of the input graph. <\/jats:p>","DOI":"10.1142\/s0129626498000407","type":"journal-article","created":{"date-parts":[[2003,9,8]],"date-time":"2003-09-08T09:56:09Z","timestamp":1063014969000},"page":"399-405","source":"Crossref","is-referenced-by-count":0,"title":["A Parallel Algorithm for Finding a Perfect Matching in a Planar Graph"],"prefix":"10.1142","volume":"08","author":[{"given":"E.","family":"Bampis","sequence":"first","affiliation":[{"name":"LaMI, Universit\u00e9 d'Evry, Boulevard des Coquibus, 91025 Evry Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Giannakos","sequence":"additional","affiliation":[{"name":"LaMI, Universit\u00e9 d'Evry, Boulevard des Coquibus, 91025 Evry Cedex, France"},{"name":"LRI, B\u00e2t 490, Universit\u00e9 de Paris Sud, 91405 Orsay Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Karzanov","sequence":"additional","affiliation":[{"name":"Institute for System Analysis, 9, Prosp. Let Octyabrya, 117312 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Manoussakis","sequence":"additional","affiliation":[{"name":"LRI, B\u00e2t 490, Universit\u00e9 de Paris Sud, 91405 Orsay Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Milis","sequence":"additional","affiliation":[{"name":"LRI, B\u00e2t 490, Universit\u00e9 de Paris Sud, 91405 Orsay Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626498000407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:33:38Z","timestamp":1565184818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626498000407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1998,9]]}},"alternative-id":["10.1142\/S0129626498000407"],"URL":"https:\/\/doi.org\/10.1142\/s0129626498000407","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,9]]}}}