{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T14:53:27Z","timestamp":1697900007294},"reference-count":13,"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>The expected costs of the matchings found by various divide\u2010and\u2010conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.<\/jats:p>","DOI":"10.1002\/net.3230130104","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:29:14Z","timestamp":1178893754000},"page":"49-66","source":"Crossref","is-referenced-by-count":13,"title":["Probabilistic analysis of divide\u2010and\u2010conquer heuristics for minimum weighted euclidean matching"],"prefix":"10.1002","volume":"13","author":[{"given":"Edward M.","family":"Reingold","sequence":"first","affiliation":[]},{"given":"Kenneth J.","family":"Supowit","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"D.Avis Two greedy heuristics for the weighted perfect matching problem. InProc. Ninth Southeastern Conf. on Combinatorics Graph Theory and Computing (1978)65\u201376."},{"key":"e_1_2_1_3_2","volume-title":"Asymptotic Methods in Analysis","author":"De Bruijn N. G.","year":"1981"},{"key":"e_1_2_1_4_2","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","year":"1968"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_6_2","unstructured":"M.Iri M.Murota andS.Matsui Linear\u2010time heuristics for the minimum\u2010weight perfect matching on a plane with an application to the plotter algorithm. Unpublished (1980)."},{"key":"e_1_2_1_7_2","volume-title":"The Art of Computer Programming, Volume 3: Searching and Sorting","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_8_2","unstructured":"C. H.Papadimitriou The probabilistic analysis of matching heuristics. inProc. Fifteenth Annual Allerton Conf. on Communication Control and Computing(1977)368\u2013378."},{"key":"e_1_2_1_9_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210050"},{"key":"e_1_2_1_11_2","unstructured":"J.Saxe personal communication (1981)."},{"key":"e_1_2_1_12_2","unstructured":"M. I.Shamos Computational Geometry Ph.D. Thesis Yale University (1978)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"K. J.Supowit D. A.Plaisted andE. M.Reingold Heuristics for weighted perfect matching.In Proc. Twelfth Annual ACM Symp. on Theory of Computing(1980)398\u2013419.","DOI":"10.1145\/800141.804689"},{"key":"e_1_2_1_14_2","article-title":"Divide\u2010and\u2010Conquer heuristics for minimum weighted Euclidean matching","author":"Supowit K. J.","journal-title":"SIAM J. Comput."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T19:57:01Z","timestamp":1697745421000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,3]]}},"alternative-id":["10.1002\/net.3230130104"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130104","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]]}}}