{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:26:21Z","timestamp":1767245181767,"version":"3.37.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,12,16]],"date-time":"2009-12-16T00:00:00Z","timestamp":1260921600000},"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":[[2011,12]]},"DOI":"10.1007\/s00453-009-9377-1","type":"journal-article","created":{"date-parts":[[2009,12,15]],"date-time":"2009-12-15T17:03:30Z","timestamp":1260896610000},"page":"898-922","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem"],"prefix":"10.1007","volume":"61","author":[{"given":"Maxim A.","family":"Babenko","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,12,16]]},"reference":[{"key":"9377_CR1","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-540-92182-0_23","volume":"5369","author":"M. Babenko","year":"2008","unstructured":"Babenko, M.: An efficient scaling algorithm for the minimum weight bibranching problem. Lect. Notes Comput. Sci. 5369, 232\u2013245 (2008)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9377_CR2","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Stein, C., Rivest, R., Leiserson, C.: Introduction to Algorithms. McGraw-Hill Higher Education, New York (2001)"},{"key":"9377_CR3","first-page":"1277","volume":"11","author":"E. Dinic","year":"1980","unstructured":"Dinic, E.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277\u20131280 (1980)","journal-title":"Sov. Math. Dokl."},{"key":"9377_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Stand. 71B, 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"2","key":"9377_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02579270","volume":"1","author":"A. Frank","year":"1981","unstructured":"Frank, A.: How to make a digraph strongly connected. Combinatorica 1(2), 145\u2013153 (1981)","journal-title":"Combinatorica"},{"issue":"3","key":"9377_CR6","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9377_CR7","unstructured":"Gabow, H.: A representation for crossing set families with applications to submodular flow problems. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 202\u2013211 (1993)"},{"key":"9377_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.: A framework for cost-scaling algorithms for submodular flow problems. In: SFCS \u201993: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, pp. 449\u2013458 (1993)","DOI":"10.1109\/SFCS.1993.366842"},{"issue":"2","key":"9377_CR9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. Gabow","year":"1986","unstructured":"Gabow, H., Galil, Z., Spencer, T., Tarjan, R.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109\u2013122 (1986)","journal-title":"Combinatorica"},{"key":"9377_CR10","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Tarjan, R.: Solving minimum-cost flow problems by successive approximation. In: STOC \u201987: Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, pp.\u00a07\u201318 (1987)","DOI":"10.1145\/28395.28397"},{"issue":"5","key":"9377_CR11","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H. Gabow","year":"1989","unstructured":"Gabow, H., Tarjan, R.: Faster scaling algorithms for network problems. SIAM J. Comput. 18(5), 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9377_CR12","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H. Gabow","year":"1991","unstructured":"Gabow, H., Tarjan, R.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"issue":"2","key":"9377_CR13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1006\/jctb.1998.1817","volume":"73","author":"J. Keijsper","year":"1998","unstructured":"Keijsper, J., Pendavingh, R.: An efficient algorithm for minimum-weight bibranching. J. Comb. Theory, Ser. B 73(2), 130\u2013145 (1998)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9377_CR14","first-page":"261","volume":"16","author":"A. Schrijver","year":"1982","unstructured":"Schrijver, A.: Min-max relations for directed graphs. Ann. Discrete Math. 16, 261\u2013280 (1982)","journal-title":"Ann. Discrete Math."},{"key":"9377_CR15","volume-title":"Combinatorial Optimization","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"issue":"3","key":"9377_CR16","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. Sleator","year":"1983","unstructured":"Sleator, D., Tarjan, R.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9377_CR17","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. Tarjan","year":"1983","unstructured":"Tarjan, R.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (1983)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9377-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9377-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9377-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T20:40:51Z","timestamp":1739479251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9377-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,16]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9377"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9377-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,12,16]]}}}