{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:14:47Z","timestamp":1773656087009,"version":"3.50.1"},"reference-count":17,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8350,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,12]]},"abstract":"Abstract<\/jats:title>In this paper we explore implementation issues related to the solution of the weighted matching problem defined on an undirected graph G<\/jats:italic> = (V, E<\/jats:italic>). We present algorithms based on the two different linear characterizations of the feasible solutions to the matching problem. Furthermore, we present two specialized implementations, one with an O<\/jats:italic> (|V<\/jats:italic>|3<\/jats:sup>) time bound and one with an O<\/jats:italic>(|V\u2016E<\/jats:italic>| log |V<\/jats:italic>|) time bound. Both of these implementations have storage requirements that are linear in |V<\/jats:italic>| and |E<\/jats:italic>|. We initially develop these algorithms as special implementations of the well\u2010known primaldual (blossom) algorithm and then show how the updates they perform have an interesting interpretation when the algorithms are viewed as methods that successively find shortest augmenting paths. Finally, we show that postoptimality analysis can be performed very efficiently within this setting.<\/jats:p>","DOI":"10.1002\/net.3230130406","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T17:18:23Z","timestamp":1178903903000},"page":"517-549","source":"Crossref","is-referenced-by-count":63,"title":["An analysis of alternative strategies for implementing matching algorithms"],"prefix":"10.1002","volume":"13","author":[{"given":"Michael O.","family":"Ball","sequence":"first","affiliation":[]},{"given":"Ulrich","family":"Derigs","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A.","year":"1974"},{"key":"e_1_2_1_3_2","unstructured":"M. O.Ball A linear\u2010time algorithm for finding a minimum\u2010weight spanning tree in graphs in which all cycles pass through a single vertex. Unpublished."},{"key":"e_1_2_1_4_2","unstructured":"M. O.BallandL. D.Bodin A computational study comparing the efficiency of various list structures in matching algorithm. Unpublished."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.17.1.4"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121194"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110407"},{"key":"e_1_2_1_8_2","unstructured":"U.Derigs Matching code theory part I: Combinatorial structures and the cardinality matching problem. Working Paper MS\/S No. 81\u2013041 College of Business and Management University of Maryland at College Park (1981)."},{"key":"e_1_2_1_9_2","unstructured":"U.Derigs Shortest augmenting paths and sensitivity analysis for optimal matchings. Report 82222\u2010OR Institut f\u00fcr \u00d6konometrie und Operations Research Universit\u00e4t Bonn (1982)."},{"key":"e_1_2_1_10_2","unstructured":"U.DerigsandG.Kazakidis On two methods for solving minimal perfect matching problems. InProceedings of the Second Danish\/Polish Mathematical Programming Seminar J. Krarup and S. Walukiewicz Eds. (1980) pp.85\u2013100."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"J.EdmondsandW. R.Pulleyblank Facets of 1\u2010matching polyhedra. InHypergraph Seminar Lecture Notes in Mathematics 411 (1974)214\u2013242.","DOI":"10.1007\/BFb0066196"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"Z.Galil S.Micali andH.Gabow Priority queries with variable priority and anO(EV log V)algorithm for finding a maximal weighted matching in general graphs. Unpublished manuscript (1982).","DOI":"10.1109\/SFCS.1982.36"},{"key":"e_1_2_1_14_2","first-page":"217","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800260401"},{"key":"e_1_2_1_16_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1976"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"W. H.Pulleyblank Faces of matching polyhedra. Thesis University of Waterloo 1973.","DOI":"10.1007\/BFb0066196"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110105"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T02:59:26Z","timestamp":1697770766000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1983,12]]}},"alternative-id":["10.1002\/net.3230130406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130406","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,12]]}}}