{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T14:51:17Z","timestamp":1697899877150},"reference-count":10,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8625,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Several linear\u2010time approximation algorithms for the minimum\u2010weight perfect matching in a plane are proposed, and their worst\u2010 and average\u2010case behaviors are analyzed theoretically as well as experimentally. A linear\u2010time approximation algorithm, named the \u201cspiral\u2010rack algorithm (with preprocess and with tour),\u201d is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.<\/jats:p>","DOI":"10.1002\/net.3230130105","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:29:12Z","timestamp":1178893752000},"page":"67-92","source":"Crossref","is-referenced-by-count":22,"title":["Heuristics for planar minimum\u2010weight perfect metchings"],"prefix":"10.1002","volume":"13","author":[{"given":"Masao","family":"Iri","sequence":"first","affiliation":[]},{"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[]},{"given":"Shouichi","family":"Matsui","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90103-4"},{"key":"e_1_2_1_4_2","first-page":"572","volume-title":"In Proc. 10th IFIP Conference on System Modeling and Optimization Lecture Notes in Control and Information Sciences, 38","author":"Iri M.","year":"1982"},{"key":"e_1_2_1_5_2","unstructured":"M.Iri K.Murota andS.Matsui Linear\u2010time heuristics for the minimum\u2010weight perfect matching on a plane with an application to the plotter algorithm. Research Memorandum RMI 81\u201307. Department of Mathematical Engineering and Instrumentation Physics University of Tokyo (1981)."},{"key":"e_1_2_1_6_2","unstructured":"M.IriandA.Taguchi The determination of the pen\u2010movement of anX Y\u2010plotter and its computational complexity (in Japanese). InProc. Spring Conference of the Operations Research Society of Japan P\u20138 1980 pp.204 205."},{"key":"e_1_2_1_7_2","volume-title":"Combinatorial Optimization\u2010Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_8_2","unstructured":"C. H.Papadimitriou The probabilistic analysis of matching heuristics. InProc. 15th Ann. Allerton Conf. on Communication Control and Computing 1977 pp.368\u2013378."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210050"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"J. M.Steele Subadditive Euclidean functional and non\u2010linear growth in geometric probability.Ann. of Probability 9(1981)365\u2013376.","DOI":"10.1214\/aop\/1176994411"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"K. J.Supowit D. A.Plaisted andE. M.Reingold Heuristics for weighted perfect matching.In Proc. 12th Ann. ACM Symp. on Theory of Computing 1980 pp.398\u2013414.","DOI":"10.1145\/800141.804689"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T19:57:05Z","timestamp":1697745425000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,3]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,3]]}},"alternative-id":["10.1002\/net.3230130105"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130105","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,3]]}}}