{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:59Z","timestamp":1725663779750},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_275","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:06:31Z","timestamp":1330257991000},"page":"506-517","source":"Crossref","is-referenced-by-count":4,"title":["Minimum weight euclidean matching and weighted relative neighborhood graphs"],"prefix":"10.1007","author":[{"given":"Andy","family":"Mirzaian","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"47_CR1","unstructured":"P.J. Agarwal and J. Matou\u0161ek. Relative neighborhood graphs in three dimensions. In Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, pages 58\u201365, 1992."},{"key":"47_CR2","unstructured":"F. Aurenhammer. Voronoi diagrams \u2014 a survey of a fundamental geometric data structure. Technical Report B 90-09, Freie Universit\u00e4t, 1990."},{"key":"47_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. J. of Research of National Bureau of Standards, 69B:125\u2013130, 1965.","journal-title":"J. of Research of National Bureau of Standards"},{"key":"47_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, trees, and flowers. Canadian J. Math., 17:449\u2013467, 1965.","journal-title":"Canadian J. Math."},{"key":"47_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153\u2013174, 1987.","journal-title":"Algorithmica"},{"key":"47_CR6","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34:596\u2013615, 1987.","journal-title":"J. ACM"},{"key":"47_CR7","unstructured":"H.N. Gabow. Implementations of algorithms for maximum matching on nonbipartite graphs. PhD thesis, Comp. Sci. Dept., Stanford Univ., 1973."},{"key":"47_CR8","unstructured":"H.N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, pages 434\u2013443, 1990."},{"key":"47_CR9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z. Galil","year":"1986","unstructured":"Z. Galil. Efficient algorithms for finding maximum matching in graphs. ACM Comp. Surveys, 18:23\u201338, 1986.","journal-title":"ACM Comp. Surveys"},{"key":"47_CR10","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z. Galil","year":"1986","unstructured":"Z. Galil, S. Micali, and H.N. Gabow. An O(EVlogV) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Computing, 15:120\u2013130, 1986.","journal-title":"SIAM J. Computing"},{"key":"47_CR11","unstructured":"J. Jarmoczyk, M. Kowaluk, and F.F. Yao. An optimal algorithm for constructing \u03b2-skeletons in Lp metric. SIAM J. Computing, to appear."},{"key":"47_CR12","volume-title":"Combinatrotial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler. Combinatrotial Optimization: Networks and Matroids. Holt, Reinhart and Winston, New York, 1976."},{"key":"47_CR13","unstructured":"L. Lov\u00e1sz and M.D. Plummer. Matching Theory. Annals of Discrete Math 29, North-Holland, 1986."},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"D.W. Matula and R.R. Sokal. Properties of Gabriel graphs relevant to geographic variation search and the clustering of points in the plane. Geogr. Analysis, pages 205\u2013222, 1980.","DOI":"10.1111\/j.1538-4632.1980.tb00031.x"},{"key":"47_CR15","unstructured":"A. Mirzaian. Optimum circle packing with specified centers, in preparation."},{"key":"47_CR16","volume-title":"Technical Report CS-92-08","author":"A. Mirzaian","year":"1992","unstructured":"A. Mirzaian. Minimum weight Euclidean matching and weighted relative neighborhood graphs. Technical Report CS-92-08, Dept. of Computer Science, York University, Canada, Sept. 1992."},{"key":"47_CR17","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"47_CR18","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/0214034","volume":"14","author":"M. Sharir","year":"1985","unstructured":"M. Sharir. Intersection and closest-pair problems for a set of planar discs. SIAM J. Computing, 14:448\u2013468, 1985.","journal-title":"SIAM J. Computing"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"G.T. Toussaint","year":"1980","unstructured":"G.T. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261\u2013268, 1980.","journal-title":"Pattern Recognition"},{"key":"47_CR20","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"P.M. Vaidya","year":"1989","unstructured":"P.M. Vaidya. Geometry helps in matching. SIAM J. Computing, 18:1201\u20131225, 1989.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_275.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:08:22Z","timestamp":1605647302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_275","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}