{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T10:08:34Z","timestamp":1776247714668,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf02579168","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:15:33Z","timestamp":1174598133000},"page":"109-122","source":"Crossref","is-referenced-by-count":393,"title":["Efficient algorithms for finding minimum spanning trees in undirected and directed graphs"],"prefix":"10.1007","volume":"6","author":[{"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[]},{"given":"Zvi","family":"Galil","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Spencer","sequence":"additional","affiliation":[]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579168_CR1","first-page":"29","volume-title":"Developments in Operations Research","author":"F. Bock","year":"1971","unstructured":"F. Bock, An algorithm to construct a minimum directed spanning tree in a directed network, in:Developments in Operations Research, Gordon and Breach, New York, 1971, 29\u201344."},{"key":"BF02579168_CR2","first-page":"37","volume":"3","author":"O. Boruvka","year":"1926","unstructured":"O. Boruvka, O jistem problemu minim\u00e1lni\u2019mPr\u00e1ca Moravsk\u00e9 Pri\u0155odov\u011bdeck\u00e9 Spol\u011bcnosti 3 (1926), 37\u201358. (In Czech).","journal-title":"Pr\u00e1ca Moravsk\u00e9 Pri\u0155odov\u011bdeck\u00e9 Spol\u011bcnosti"},{"key":"BF02579168_CR3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230090403","volume":"9","author":"P. M. Camerini","year":"1979","unstructured":"P. M. Camerini, L. Fratta andF. Maffioli, A note on finding optimum branchings,Networks 9 (1979), 309\u2013312.","journal-title":"Networks"},{"key":"BF02579168_CR4","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"D. Cheriton andR. E. Tarjan, Finding minimum spanning trees,SIAM J. Comput. 5 (1976), 724\u2013742.","journal-title":"SIAM J. Comput."},{"key":"BF02579168_CR5","first-page":"1396","volume":"14","author":"Y. J. Chu","year":"1965","unstructured":"Y. J. Chu andT. H. Liu, On the shortest arborescence of a directed graph,Sci. Sinica 14 (1965), 1396\u20131400.","journal-title":"Sci. Sinica"},{"key":"BF02579168_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Optimum branchings,J. Res. Nat. Bur. Standards 71B (1967), 233\u2013240.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"BF02579168_CR7","doi-asserted-by":"crossref","unstructured":"M. L. Fredman andR. E. Tarjan, Fibonacci heaps and their uses in network optimization algorithms,J. Assoc. Comput. Mach., to appear; also Proc. 25 th Annual IEEE Symp. on Found. of Comp. Sci. (1984), 338\u2013346.","DOI":"10.1109\/SFCS.1984.715934"},{"key":"BF02579168_CR8","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, Z. Galil andT. H. Spencer, Efficient implementation of graph algorithms using contraction,Proc. 25 th Annual IEEE Symp. on Found. of Comp. Sci. (1984), 347\u2013357.","DOI":"10.1109\/SFCS.1984.715935"},{"key":"BF02579168_CR9","unstructured":"H. N. Gabow, Z. Galil andT. Spencer, Efficient implementation of graph algorithms using contraction,J. Assoc. Comput. Mach., submitted."},{"key":"BF02579168_CR10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0196-6774(84)90042-7","volume":"5","author":"H. N. Gabow","year":"1984","unstructured":"H. N. Gabow andR. E. Tarjan, Efficient algorithms for a family of matroid intersection problems,J. Algorithms 5 (1984), 80\u2013131.","journal-title":"J. Algorithms"},{"key":"BF02579168_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham andP. Hell, On the history of the minimum spanning tree problem,Ann. History of Computing 7 (1985), 43\u201357.","journal-title":"Ann. History of Computing"},{"key":"BF02579168_CR12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1002\/net.3230010305","volume":"1","author":"R. M. Karp","year":"1971","unstructured":"R. M. Karp, A simple derivation of Edmonds\u2019 algorithm for optimum branchings,Networks 1 (1971), 265\u2013272.","journal-title":"Networks"},{"key":"BF02579168_CR13","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02579443","volume":"5","author":"J. Koml\u00f3s","year":"1985","unstructured":"J. Koml\u00f3s, Linear verification for spanning trees,Combinatorica 5 (1985), 57\u201365.","journal-title":"Combinatorica"},{"key":"BF02579168_CR14","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, Efficiency of a good but not linear set union algorithm,J. Assoc. Comput. Mach. 22 (1975), 215\u2013225.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02579168_CR15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R. E. Tarjan","year":"1977","unstructured":"R. E. Tarjan, Finding optimum branchings,Networks 7 (1977), 25\u201335.","journal-title":"Networks"},{"key":"BF02579168_CR16","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan, Applications of path compression on balanced trees,J. Assoc. Comput. Mach. 26 (1979), 690\u2013715.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02579168_CR17","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"BF02579168_CR18","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan andJ. Van Leeuwen, Worst-case analysis of set union algorithms,J. Assoc. Comput. Mach. 31 (1984), 245\u2013281.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02579168_CR19","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, Amortized computational complexity,SIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"BF02579168_CR20","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(75)90056-3","volume":"4","author":"A. Yao","year":"1975","unstructured":"A. Yao, AnO(|E|log log|V|) algorithm for finding minimum spanning trees,Inform. Process. Lett. 4 (1975), 21\u201323.","journal-title":"Inform. Process. Lett."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579168.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579168\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T05:05:34Z","timestamp":1736917534000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF02579168"],"URL":"https:\/\/doi.org\/10.1007\/bf02579168","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}