{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T12:14:35Z","timestamp":1742645675913,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T00:00:00Z","timestamp":1684368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T00:00:00Z","timestamp":1684368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00453-023-01127-x","type":"journal-article","created":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T08:03:10Z","timestamp":1684396990000},"page":"3214-3289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Weight-Scaling Algorithm for f-Factors of Multigraphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9775-3492","authenticated-orcid":false,"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,18]]},"reference":[{"key":"1127_CR1","unstructured":"Brand, J.V.D., Lee, Y.T., Liu, Y.P., Saranurak, T., Sidford, A., Song, Z., Wang, D.: Minimum cost flows, MDPs, and $$\\ell _1$$-regression in nearly linear time for dense instances. In: Proc. 53 Annual ACM Symp. on Theory of Comp., pp. 859\u2013869 (2021)"},{"key":"1127_CR2","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley and Sons, New York (1998)"},{"key":"1127_CR3","unstructured":"Duan, R., He, H., Zhang, T.: A scaling algorithm for weighted f-factors in general graphs. In: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), vol. 168 of LIPIcs, pp. 41:1\u201341:17 (2020)"},{"issue":"1","key":"1127_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3155301","volume":"14","author":"R Duan","year":"2018","unstructured":"Duan, R., Pettie, S., Su, H.-H.: Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms 14(1), 1\u201335 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"1127_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand. 69B, 125\u2013130 (1965)","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"1127_CR6","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4, 507\u2013518 (1975)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1127_CR7","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"1127_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: Proc. 26th Annual Symp. on Found. of Comp. Sci., pp. 90\u2013100 (1985)","DOI":"10.1109\/SFCS.1985.3"},{"key":"1127_CR9","unstructured":"Gabow, H.N.: Blocking trails for $$f$$-factors of multigraphs. arXiv:2112.04096"},{"issue":"3","key":"1127_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3183369","volume":"14","author":"HN Gabow","year":"2018","unstructured":"Gabow, H.N.: Data structures for weighted matching and extensions to $$b$$-matching and $$f$$-factors. ACM Trans. Algorithms 14(3), 1\u201380 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1127_CR11","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. J. ACM 23(2), 221\u2013234 (1976)","journal-title":"J. ACM"},{"issue":"1\u20134","key":"1127_CR12","first-page":"109","volume":"154","author":"HN Gabow","year":"2017","unstructured":"Gabow, H.N.: The weighted matching approach to maximum cardinality matching. Fund. Inform. 154(1\u20134), 109\u2013130 (2017)","journal-title":"Fund. Inform."},{"issue":"2","key":"1127_CR13","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1127_CR14","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"HN Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18(5), 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1127_CR15","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"1127_CR16","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Micali, S., Gabow, H.N.: An $$O(EV \\log V)$$ algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15(1), 120\u2013130 (1986)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1127_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An $$n^{5 \/ 2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"1127_CR18","doi-asserted-by":"publisher","first-page":"1952","DOI":"10.1007\/s00453-022-00949-5","volume":"84","author":"D Huang","year":"2022","unstructured":"Huang, D., Pettie, S.: Approximate generalized matching: $$f$$-matchings and $$f$$-edge covers. Algorithmica 84(7), 1952\u20131992 (2022)","journal-title":"Algorithmica"},{"key":"1127_CR19","first-page":"81","volume":"5","author":"AV Karzanov","year":"1973","unstructured":"Karzanov, A.V.: On finding maximum flows in network with special structure and some applications. Mat. Vopr. Upr. Proizvod. 5, 81\u201394 (1973). ((In Russian.))","journal-title":"Mat. Vopr. Upr. Proizvod."},{"key":"1127_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Log. Q. 2, 83\u201397 (1955)","journal-title":"Naval Res. Log. Q."},{"key":"1127_CR21","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"key":"1127_CR22","volume-title":"Matching Theory, North-Holland Mathematic Studies","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, North-Holland Mathematic Studies, vol. 121. North-Holland, New York (1986)"},{"key":"1127_CR23","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|V|} \\cdot |E|)$$ algorithm for finding maximum matching in general graphs. In: Proc. 21st Annual Symp. on Found. of Comp. Sci., 21st, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"1127_CR24","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York (2003)"},{"issue":"4","key":"1127_CR25","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM 26(4), 690\u2013715 (1979)","journal-title":"J. ACM"},{"issue":"3","key":"1127_CR26","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362\u2013394 (1999)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01127-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:08:31Z","timestamp":1695737311000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01127-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,18]]},"references-count":26,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1127"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01127-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,5,18]]},"assertion":[{"value":"1 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}