{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T15:18:46Z","timestamp":1697210326789},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,4,1]],"date-time":"1995-04-01T00:00:00Z","timestamp":796694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,4]]},"DOI":"10.1007\/bf01293485","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T22:39:41Z","timestamp":1111703981000},"page":"357-380","source":"Crossref","is-referenced-by-count":11,"title":["New primal and dual matching heuristics"],"prefix":"10.1007","volume":"13","author":[{"given":"M.","family":"J\ufffdnger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W.","family":"Pulleyblank","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A. V., Hopcroft, J. E., and Ullman, D. U. (1974).The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/B978-0-444-87806-9.50011-6","volume-title":"Computational Geometry","author":"T. Asano","year":"1985","unstructured":"Asano, T., Edahiro, M., Imai, H., Iri, M., and Murota, K. (1985). Practical use of bucketing techniques in computational geometry. In: G. T. Toussaint (ed.),Computational Geometry, North-Holland, Amsterdam, 1985, pp. 153?195."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D. Avis","year":"1983","unstructured":"Avis, D. (1983). A survey of heuristics for the weighted matching problem.Networks,13 (1983), 475?493.","journal-title":"Networks"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J. Beardwood","year":"1959","unstructured":"Beardwood, J., Halton, J. H., and Hammersley, J. M. (1959). The shortest path through many points.Proceedings of the Cambridge Philosophical Society,55 (1959), 299?327.","journal-title":"Proceedings of the Cambridge Philosophical Society"},{"key":"CR5","volume-title":"Technical Report","author":"N. Christofides","year":"1976","unstructured":"Christofides, N. (1976). Worst case analysis of a new heuristic for the travelling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01588956","volume":"14","author":"G. Cornu\ufffdjols","year":"1978","unstructured":"Cornu\ufffdjols, G., and Nemhauser, G. L. (1978). Tight bounds for Christofides' traveling salesman heuristic.Mathematical Programming,14 (1978), 116?121.","journal-title":"Mathematical Programming"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/BFb0121194","volume":"8","author":"W. H. Cunningham","year":"1978","unstructured":"Cunningham, W. H., and Marsh, A. (1978). A primal algorithm for optimum matching.Mathematical Programming Study,8 (1978), 50?72.","journal-title":"Mathematical Programming Study"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230160102","volume":"16","author":"U. Derigs","year":"1986","unstructured":"Derigs, U. (1986). Solving large scale matching problems efficiently-a new primal matching approach.Networks,16 (1986), 1?16.","journal-title":"Networks"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J. (1965a). Paths, trees and flowers.Canadian Journal of Mathematics,17 (1965), 449?457.","journal-title":"Canadian Journal of Mathematics"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J. (1965b). Maximum matching and a polyhedron with 0?1 vertices.Journal of Research of the National Bureau of Standards,69B (1965), 125?130.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"CR11","first-page":"307","volume-title":"A general approximation technique for constrained forest problems","author":"M. X. Goemans","year":"1992","unstructured":"Goemans, M. X., and Williamson, D. P. (1992). A general approximation technique for constrained forest problems.Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, New York, 1992, pp. 307?316."},{"key":"CR12","volume-title":"Technical Report LCSR-TR-69","author":"M. D. Grigoriadis","year":"1985","unstructured":"Grigoriadis, M. D., and Kalantari, B. (1985a). A lower bound to the complexity of Euclidean and rectilinear matching algorithms. Technical Report LCSR-TR-69, Department of Computer Science, Rutgers University, New Brunswick, NJ, 1985."},{"key":"CR13","volume-title":"Technical Report LCSR-TR-76","author":"M. D. Grigoriadis","year":"1985","unstructured":"Grigoriadis, M. D., and Kalantari, B. (1985b). A new class of heuristic algorithms for weighted perfect matching. Technical Report LCSR-TR-76, Department of Computer Science, Rutgers University, New Brunswick, NJ, 1985."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01584376","volume":"33","author":"M. Gr\ufffdtschel","year":"1985","unstructured":"Gr\ufffdtschel, M., and Holland, O. (1985). Solving matching problems with linear programming.Mathematical Programming,33 (1985), 243?259.","journal-title":"Mathematical Programming"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01415960","volume":"35","author":"M. Gr\ufffdtschel","year":"1991","unstructured":"Gr\ufffdtschel, M., J\ufffdnger, M., and Reinelt, G. (1991). Optimal control of plotting and drilling machines: a case study.ZOR-Methods and Models of Operations Research,35 (1991), 61?84.","journal-title":"ZOR-Methods and Models of Operations Research"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/net.3230130105","volume":"13","author":"M. Iri","year":"1983","unstructured":"Iri, M., Murota, K., and Matsui, S. (1983), Heuristics for planar minimum weight perfect matchings.Networks,13 67?92.","journal-title":"Networks"},{"key":"CR17","first-page":"1","volume-title":"Jahrbuch \ufffdberblick Mathematik","author":"M. J\ufffdnger","year":"1993","unstructured":"J\ufffdnger, M., and Pulleyblank, W. R. (1993). Geometric duality and combinatorial optimization. In: S. D. Chatterji, B. Fuchssteiner, U. Kulisch, and R. Liedl (eds.),Jahrbuch \ufffdberblick Mathematik 1993, Vieweg, Braunschweig\/Wiesbaden, 1993, pp. 1?24."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF02242021","volume":"47","author":"M. J\ufffdnger","year":"1991","unstructured":"J\ufffdnger, M., Reinelt, G., and Zepf, D. (1991). Computing correct Delaunay triangulations.Computing,47 (1991), 43?49.","journal-title":"Computing"},{"key":"CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K. (1984).Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry. Springer-Verlag, Berlin, 1984."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"306","DOI":"10.15807\/jorsj.27.306","volume":"27","author":"T. Ohya","year":"1984","unstructured":"Ohya, T., Iri, M., and Murota, K. (1984). Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms.Journal of the Operations Research Society of Japan,27 (1984), 306?337.","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"CR21","unstructured":"Papadimitriou, C. H. (1977). The probabilistic analysis of matching heuristics.Proceedings of the 15thAllerton Conference on Communication, Control and Computing, 1977, pp. 368?378."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"E. M. Reingold","year":"1981","unstructured":"Reingold, E. M., and Tarjan, R. E. (1981). On a greedy heuristic for complete matching.SIAM Journal on Computing,10 (1981), 676?681.","journal-title":"SIAM Journal on Computing"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"Shamos, M. I. (1975). Geometric complexity.Proceedings of the 1th Annual ACM Symposium on Theory of Computing, 1975, pp. 224?233.","DOI":"10.1145\/800116.803772"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"Shamos, M. I., and Hoey, D. (1975). Closest point problems.Proceedings of the 16th IEEE Annual Symposium on the Foundations of Computer Science, 1975, pp. 151?162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"CR25","unstructured":"Sugihara, K. (1988). A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction. Research Memorandum RMI 88-14, Faculty of Engineering, University of Tokyo, 1988."},{"key":"CR26","unstructured":"Sugihara, K., and Iri, M. (1988). Geometric algorithms in finite precision arithmetic. Research Memorandum RMI 88-10, Faculty of Engineering, University of Tokyo, 1988."},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"Supowit, K. J., Plaisted, D. A., and Reingold, E. M. (1980). Heuristics for weighted perfect matching.Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980, pp. 398?419.","DOI":"10.1145\/800141.804689"},{"key":"CR28","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data structures and network algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"Tarjan, R. E. (1983). Data structures and network algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"key":"CR29","unstructured":"Weber, M., and Liebling, T. M. (1985). Euclidean matching problems and the Metropolis algorithm. Technical Report, D\ufffdpartment de Math\ufffdmatiques, EPF Lausanne, 1985."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293485.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293485\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T07:18:31Z","timestamp":1556781511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["BF01293485"],"URL":"https:\/\/doi.org\/10.1007\/bf01293485","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}