{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T01:07:23Z","timestamp":1775696843000,"version":"3.50.1"},"reference-count":13,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"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":["Information Processing Letters"],"published-print":{"date-parts":[[1986,1]]},"DOI":"10.1016\/0020-0190(86)90143-2","type":"journal-article","created":{"date-parts":[[2003,3,25]],"date-time":"2003-03-25T15:53:30Z","timestamp":1048607610000},"page":"73-76","source":"Crossref","is-referenced-by-count":7,"title":["A lower bound to the complexity of Euclidean and rectilinear matching algorithms"],"prefix":"10.1016","volume":"22","author":[{"given":"M.D.","family":"Grigoriadis","sequence":"first","affiliation":[]},{"given":"B.","family":"Kalantari","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0020-0190(86)90143-2_BIB1","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1002\/net.3230130404","article-title":"A survey of heuristics for the weighted matching problem","volume":"13","author":"Avis","year":"1983","journal-title":"Networks"},{"key":"10.1016\/0020-0190(86)90143-2_BIB2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","article-title":"Decomposable searching problems I: Static to dynamic transformations","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0190(86)90143-2_BIB3","series-title":"Tech. Rept.","article-title":"Worst-case analysis of a new heuristic for the traveling salesman problem","author":"Christofides","year":"1976"},{"key":"10.1016\/0020-0190(86)90143-2_BIB4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","article-title":"Matching and a polyhedron with 0\u20131 vertices","volume":"69B","author":"Edmonds","year":"1965","journal-title":"J. Res. Nat. Bur. Standards Serie"},{"key":"10.1016\/0020-0190(86)90143-2_BIB5","series-title":"23rd Ann. IEEE Symp. on Foundations of Computer Science","first-page":"255","article-title":"Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs","author":"Galil","year":"1982"},{"key":"10.1016\/0020-0190(86)90143-2_BIB6","article-title":"Implementation of algorithms on nonbipartite graphs","author":"Gabow","year":"1973"},{"key":"10.1016\/0020-0190(86)90143-2_BIB7","series-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler","year":"1976"},{"key":"10.1016\/0020-0190(86)90143-2_BIB8","series-title":"EATCS Monographs on Theoretical Computer Science","article-title":"Data Structures and Algorithms 1: Sprting and Searching","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/0020-0190(86)90143-2_BIB9","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0020-0190(86)90143-2_BIB10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0196-6774(84)90024-5","article-title":"Heuristic matching for graphs satisfying the triangle inequality","volume":"5","author":"Plaisted","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0190(86)90143-2_BIB11","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0210050","article-title":"On a greedy heuristic for complete matching","volume":"10","author":"Reingold","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0020-0190(86)90143-2_BIB12","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1287\/opre.26.5.718","article-title":"Combinatorial problems: Reducibility and approximation","volume":"26","author":"Sahni","year":"1978","journal-title":"Oper. Res."},{"key":"10.1016\/0020-0190(86)90143-2_BIB13","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","article-title":"Data Structures and Network Algorithms","author":"Tarjan","year":"1983"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0020019086901432?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0020019086901432?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,24]],"date-time":"2019-03-24T17:29:44Z","timestamp":1553448584000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0020019086901432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["0020019086901432"],"URL":"https:\/\/doi.org\/10.1016\/0020-0190(86)90143-2","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}