{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:06:09Z","timestamp":1743138369826,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425120"},{"type":"electronic","value":"9783540446910"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44691-5_3","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T22:32:07Z","timestamp":1180823527000},"page":"23-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Implementation of O(nmlog n) Weighted Matchings in General Graphs. The Power of Data Structures"],"prefix":"10.1007","author":[{"given":"Kurt","family":"Mehlhorn","sequence":"first","affiliation":[]},{"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"3_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullmann. The design and analysis of computer algorithms. Addison-Wesley, 1974."},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"D. Applegate and W. Cook. Solving large-scale matching problems. In D. Johnson and C.C. McGeoch, editors, Network Flows and Matchings, volume 12 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 557\u2013576. American Mathematical Society, 1993.","DOI":"10.1090\/dimacs\/012\/22"},{"key":"3_CR3","unstructured":"B. Cherkassky and A. Goldberg. PRF, a Maxflow Code. \nhttp:\/\/www.intertrust.com\/star\/goldberg\/index.html\n\n."},{"key":"3_CR4","unstructured":"W. Cook and A. Rohe. Computing minimum-weight perfect matchings. Technical Report 97863, Forschungsinstitut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn, 1997."},{"key":"3_CR5","first-page":"263","volume":"36","author":"U. Derigs","year":"1986","unstructured":"U. Derigs and A. Metz. On the use of optimal fractional matchings for solving the (integer) matching problem. Mathematical Programming, 36:263\u2013270, 1986.","journal-title":"Mathematical Programming"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01594929","volume":"50","author":"U. Derigs","year":"1991","unstructured":"U. Derigs and A. Metz. Solving (large scale) matching problems combinatorially. Mathematical Programming, 50:113\u2013122, 1991.","journal-title":"Mathematical Programming"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/BF02187810","volume":"5","author":"M.B. Dillencourt","year":"1990","unstructured":"M.B. Dillencourt. Toughness and delaunay triangulations. Discrete and Computational Geometry, 5:575\u2013601, 1990.","journal-title":"Discrete and Computational Geometry"},{"key":"3_CR8","doi-asserted-by":"publisher","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. Journal of Research of the National Bureau of Standards, 69B:125\u2013130, 1965.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"J. Edmonds. Paths, trees, and flowers. Canadian Journal on Mathematics, pages 449\u2013467, 1965.","DOI":"10.4153\/CJM-1965-045-4"},{"key":"3_CR10","unstructured":"H. N. Gabow. Implementation of algorithms for maximum matching and nonbipartite graphs. PhD thesis, Stanford University, 1974."},{"key":"3_CR11","unstructured":"H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In David Johnson, editor, Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u2019 90), pages 434\u2013443, San Francisco, CA, USA, January 1990. SIAM."},{"key":"3_CR12","doi-asserted-by":"publisher","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(EV log V ) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Computing, 15:120\u2013130, 1986.","journal-title":"SIAM J. Computing"},{"key":"3_CR13","volume-title":"Implementierung von Flu\u03b2algorithmen mit dynamischen B\u00e4umen","author":"M. Humble","year":"1996","unstructured":"M. Humble. Implementierung von Flu\u03b2algorithmen mit dynamischen B\u00e4umen. Master\u2019s thesis, Fachbereich Informatik, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 1996."},{"key":"3_CR14","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976."},{"key":"3_CR15","unstructured":"K. Mehlhorn and S. N\u00e4her. The LEDA Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999. 1018 pages."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data structures and algorithms. Volume 1: Sorting and searching, volume 1 of EATCS monographs on theoretical computer science. Springer, 1984.","DOI":"10.1007\/978-3-642-69672-5_2"},{"key":"3_CR17","volume-title":"Weighted matchings in general graphs","author":"G. Sch\u00e4fer","year":"2000","unstructured":"G. Sch\u00e4fer. Weighted matchings in general graphs. Master\u2019s thesis, Fachbereich Informatik, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 2000."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44691-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T13:05:01Z","timestamp":1588165501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44691-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425120","9783540446910"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44691-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"24 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}