{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T18:17:44Z","timestamp":1790965064391,"version":"4.1.0"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>\n                    Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x \/ log (x\n                    <jats:sup>2<\/jats:sup>\n                    \/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an $O(\\sqrt{n}W \/ k(n, W\/N))$-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G - {u} for all nodes u in O(W) time.\n                  <\/jats:p>","DOI":"10.1137\/s0097539799361208","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"18-26","source":"Crossref","is-referenced-by-count":33,"title":["A Decomposition Theorem for Maximum Weight Bipartite Matchings"],"prefix":"10.1137","volume":"31","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hing-Fung","family":"Ting","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":", Graph theory with applications to algorithms and computer science, Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4\u20138, 1984, A Wiley\u2010Interscience Publication, John Wiley & Sons Inc., 1985, 0\u20130, xv+81086g:05026"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90030-7"},{"key":"R3","volume-title":"Introduction to algorithms","author":"Manber Udi","year":"1989"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1065"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6502"},{"key":"R9","unstructured":"A. M. H. Gerards,\n                      Matching\n                      , in Handbooks in Operations Reserach and Management Science 7: Network Models, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds., North\u2010Holland, Amsterdam, 1995, pp. 135\u2013224."},{"key":"R10","unstructured":"G. H. Hardy, J. E. Littlewood, and G. P\u00f3lya,\n                      Inequalities\n                      , Cambridge University Press, Cambridge, UK, 1988."},{"key":"R10","unstructured":"Reprint of the 1952 edition."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"R12","unstructured":"Ming\u2010Yang Kao, Tak Lam, Wing Sung, Hing Ting, All\u2010cavity maximum matchings, Lecture Notes in Comput. Sci., Vol. 1350, Springer, Berlin, 1997, 364\u201337399h:05092"},{"key":"R13","unstructured":"Ming\u2010Yang Kao, Tak\u2010Wah Lam, Wing\u2010Kin Sung, Hing\u2010Fung Ting, A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees, Lecture Notes in Comput. Sci., Vol. 1643, Springer, Berlin, 1999, 438\u20134492000i:05171"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797332275"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799361208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:14Z","timestamp":1787336414000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799361208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539799361208"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799361208","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}