{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T03:33:11Z","timestamp":1778124791921,"version":"3.51.4"},"reference-count":23,"publisher":"Elsevier BV","issue":"8","license":[{"start":{"date-parts":[[2001,7,1]],"date-time":"2001-07-01T00:00:00Z","timestamp":993945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers & Operations Research"],"published-print":{"date-parts":[[2001,7]]},"DOI":"10.1016\/s0305-0548(00)00007-1","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T17:16:12Z","timestamp":1027617372000},"page":"767-785","source":"Crossref","is-referenced-by-count":77,"title":["Minimum-weight spanning tree algorithms A survey and empirical study"],"prefix":"10.1016","volume":"28","author":[{"given":"C\u00fcneyt","family":"F. Bazlama\u00e7c\u0131","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khalil","family":"S. Hindi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0305-0548(00)00007-1_BIB1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.1975.5.2.129","article-title":"Bibliography on algorithms for shortest path, shortest spanning tree and related circuit routing problems (1956\u20131974)","volume":"5","author":"Pierce","year":"1975","journal-title":"Networks"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB2","doi-asserted-by":"crossref","unstructured":"Maffioli F. Complexity of optimum undirected tree problems: a survey of recent results. In: Ausiello G, Lucertini M, editors. Analysis and design of algorithms in combinatorial optimization. International Center for Mechanical Sciences. CISM Courses and Lectures, 266. New York: Springer, 1981. p. 107\u201328.","DOI":"10.1007\/978-3-7091-2748-3_6"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","article-title":"On the history of the minimum spanning tree problem","volume":"7","author":"Graham","year":"1985","journal-title":"Annals of the History of Computing"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB4","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","article-title":"A randomized linear-time algorithm to find minimum spanning trees","volume":"42\/2","author":"Karger","year":"1995","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1137\/0905012","article-title":"Computational methods for minimum spanning tree algorithms","volume":"5\/1","author":"Haymond","year":"1984","journal-title":"SIAM Journal on Scientific and Statistical Computing"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB6","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0377-2217(92)90317-3","article-title":"An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem","volume":"56","author":"Glover","year":"1992","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB7","doi-asserted-by":"crossref","unstructured":"Moret BME, Shapiro D. How to find a minimum spanning tree in practice. In: Maurer H, editor. New results and new trends in computer science: proceedings, Graz, Austria, June 1991. Lecture Notes in Computer Science, Vol. 555. Berlin: Springer, 1991. p. 192\u2013203.","DOI":"10.1007\/BFb0038190"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB8","series-title":"Network optimization","author":"Balakrishnan","year":"1995"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB9","series-title":"Graphs and Algorithms","author":"Gondran","year":"1984"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB10","doi-asserted-by":"crossref","unstructured":"Tarjan RE. Data structures and network algorithms. In CBMS-NFS Regional Conference Series in Applied Mathematics. Philadelphia: Society for Industrial and Applied Mathematics, 1983. p. 44.","DOI":"10.1137\/1.9781611970265"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB11","unstructured":"Boruvka O. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u0131\u0301m. Pr\u00e1ca Moravsk\u00e9 P\u0159\u0131\u0301rodov\u011bdeck\u00e9 Spole\u010dnosti 1926;3:37\u201358 [in Czech], cited in [3,10]."},{"key":"10.1016\/S0305-0548(00)00007-1_BIB12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proceedings of the American Mathematical Society"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB13","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell System Technical Journal"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(75)90001-0","article-title":"Priority queues with update and finding minimum spanning trees","volume":"4","author":"Johnson","year":"1975","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(75)90056-3","article-title":"An O(|E|log log |V|) algorithm for finding minimum spanning trees","volume":"4","author":"Yao","year":"1975","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB16","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","article-title":"Finding minimum spanning trees","volume":"5","author":"Cheriton","year":"1976","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB17","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimisation algorithms","volume":"34\/3","author":"Fredman","year":"1987","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","article-title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","volume":"6","author":"Gabow","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB19","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/0221070","article-title":"Verification and sensitivity analysis of minimum spanning trees in linear time","volume":"21","author":"Dixon","year":"1992","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB20","doi-asserted-by":"crossref","unstructured":"King V. A simpler minimum spanning tree verification algorithm. In: Akl SG, Dehne F. editors. Algorithms and data structures: Proceedings of the 4th International Workshop, Kingston, Canada. Lecture Notes in Computer Science, 955. Berlin: Springer, 1995. p. 440\u20138.","DOI":"10.1007\/3-540-60220-8_83"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB21","unstructured":"Bazlama\u00e7c\u0131 CF. Optimised network design: minimum spanning trees and minimum concave-cost problems. Ph.D. thesis, University of Manchester, Institute of Science and Technology, Manchester, England, 1996."},{"key":"10.1016\/S0305-0548(00)00007-1_BIB22","doi-asserted-by":"crossref","unstructured":"Karger DR. Random sampling in matroids, with applications to graph connectivity and minimum spanning trees. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science. Los Alamitos, California: IEEE Computer Society Press, 1993. pp. 84\u201393.","DOI":"10.1109\/SFCS.1993.366879"},{"key":"10.1016\/S0305-0548(00)00007-1_BIB23","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","article-title":"Maintenance of a minimum spanning forest in a dynamic plane graph","volume":"13","author":"Eppstein","year":"1992","journal-title":"Journal of Algorithms"}],"container-title":["Computers & Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054800000071?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054800000071?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T04:08:56Z","timestamp":1578888536000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0305054800000071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,7]]},"references-count":23,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2001,7]]}},"alternative-id":["S0305054800000071"],"URL":"https:\/\/doi.org\/10.1016\/s0305-0548(00)00007-1","relation":{},"ISSN":["0305-0548"],"issn-type":[{"value":"0305-0548","type":"print"}],"subject":[],"published":{"date-parts":[[2001,7]]}}}