{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T02:28:20Z","timestamp":1769221700015,"version":"3.49.0"},"reference-count":15,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1990,6]]},"DOI":"10.1016\/0196-6774(90)90001-u","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"153-184","source":"Crossref","is-referenced-by-count":43,"title":["Generalized planar matching"],"prefix":"10.1016","volume":"11","author":[{"given":"Fran","family":"Berman","sequence":"first","affiliation":[]},{"given":"David","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Tom","family":"Leighton","sequence":"additional","affiliation":[]},{"given":"Peter W","family":"Shor","sequence":"additional","affiliation":[]},{"given":"Larry","family":"Snyder","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(90)90001-U_BIB1","series-title":"Proc. 24th IEEE Symp. on Found. of Comput. Sci.","first-page":"265","article-title":"Approximation algorithms for NP-complete problems on planar graphs","author":"Baker","year":"1983"},{"key":"10.1016\/0196-6774(90)90001-U_BIB2","author":"Berlekamp","year":"1982"},{"key":"10.1016\/0196-6774(90)90001-U_BIB3","series-title":"Blue Chip Technical Report","article-title":"Optimal Tile Salvage","author":"Berman","year":"1983"},{"key":"10.1016\/0196-6774(90)90001-U_BIB4","series-title":"CMU Graduate School of Industrial Administration Technical Report","article-title":"On the Complexity of Partitioning Graphs into Connected Subgraphs","author":"Dyer","year":"1983"},{"key":"10.1016\/0196-6774(90)90001-U_BIB5","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","article-title":"Planar 3DM is NP-complete","volume":"7","author":"Dyer","year":"1986","journal-title":"J. Algorithms"},{"issue":"No. 3","key":"10.1016\/0196-6774(90)90001-U_BIB6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","article-title":"Optimal packing and covering in the plane are NP-complete","volume":"12","author":"Fowler","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(90)90001-U_BIB7","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0097-3165(81)90016-9","article-title":"Computing a perfect strategy for n \u00d7 n chess requires exponential time in n","volume":"31","author":"Fraenkel","year":"1981","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/0196-6774(90)90001-U_BIB8","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"No. 2","key":"10.1016\/0196-6774(90)90001-U_BIB9","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0196-6774(82)90018-9","article-title":"The NP-completeness column: An ongoing guide","volume":"3","author":"Johnson","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(90)90001-U_BIB10","series-title":"Proc. 10th Ann. ACM Symp. on Theory of Computing","first-page":"240","article-title":"On the completeness of a generalized matching problem","author":"Kirkpatrick","year":"1978"},{"issue":"No. 2","key":"10.1016\/0196-6774(90)90001-U_BIB11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","article-title":"Planar formulae and their uses","volume":"11","author":"Lichtenstein","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(90)90001-U_BIB12","series-title":"A Conf. of Theoret. Comput. Sci., Univ. of Waterloo","article-title":"A separator theorem for planar graphs","author":"Lipton","year":"1977"},{"key":"10.1016\/0196-6774(90)90001-U_BIB13","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/0213018","article-title":"N by N checkers is exptime-complete","volume":"13","author":"Robson","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(90)90001-U_BIB14","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","article-title":"Rectilinear planar layouts and bipolar orientations of planar graphs","volume":"1","author":"Rosenstiehl","year":"1986","journal-title":"Discrete Comput. Geom."},{"issue":"No. 2","key":"10.1016\/0196-6774(90)90001-U_BIB15","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","article-title":"Universality considerations in VLSI circuits","author":"Valiant","year":"1981","journal-title":"IEEE Trans. Comput."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:019667749090001U?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:019667749090001U?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T06:54:09Z","timestamp":1548744849000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/019667749090001U"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["019667749090001U"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(90)90001-u","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}