{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T13:34:25Z","timestamp":1754487265181},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01994879","type":"journal-article","created":{"date-parts":[[2005,8,4]],"date-time":"2005-08-04T20:22:09Z","timestamp":1123186929000},"page":"237-248","source":"Crossref","is-referenced-by-count":10,"title":["Finding thek smallest spanning trees"],"prefix":"10.1007","volume":"32","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01994879_CR1","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor,A linear time algorithm for computing the Voronoi diagram of a convex polygon, Discrete and Comput. Geom. 4, 1989, 591\u2013604.","journal-title":"Discrete and Comput. Geom."},{"key":"BF01994879_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, H. Imai, N. Katoh, and S. Suri,Finding k points with minimum diameter and related problems, J. Algorithms, to appear.","DOI":"10.1016\/0196-6774(91)90022-Q"},{"key":"BF01994879_CR3","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. Wein,Computational Geometry, MIT LCS Research Seminar Series 3, 1988.","DOI":"10.1007\/BF01762120"},{"key":"BF01994879_CR4","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1972","unstructured":"M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan,Time bounds for selection, J. Comput. Syst. Sci. 7, 1972, 448\u2013461.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF01994879_CR5","unstructured":"H. Booth and J. Westbrook,Linear algorithms for analysis of minimum spanning and shortest path trees in planar graphs, Tech. Rep. TR-763, Department of Computer Science, Yale University, Feb. 1990."},{"key":"BF01994879_CR6","first-page":"461","volume":"19","author":"R. N. Burns","year":"1974","unstructured":"R. N. Burns and C. E. Haff,A ranking problem in graphs, 5th Southeast Conf. Combinatorics, Graph Theory and Computing 19, 1974, 461\u2013470.","journal-title":"5th Southeast Conf. Combinatorics, Graph Theory and Computing"},{"key":"BF01994879_CR7","series-title":"Int. Rep.","volume-title":"The k shortest spanning trees of a graph","author":"P. M. Camerini","year":"1974","unstructured":"P. M. Camerini, L. Fratta, and F. Maffioli,The k shortest spanning trees of a graph, Int. Rep. 73-10, IEEE-LCE Politechnico di Milano, Italy, 1974."},{"key":"BF01994879_CR8","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"D. Cheriton and R. E. Tarjan,Finding minimum spanning trees, SIAM J. Comput. 5, 1976, 310\u2013313.","journal-title":"SIAM J. Comput."},{"key":"BF01994879_CR9","unstructured":"L. P. Chew and S. Fortune,Sorting helps for Voronoi diagrams, 13th Symp. Mathematical Progr., Japan, 1988."},{"key":"BF01994879_CR10","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BFb0028278","volume":"519","author":"D. Eppstein","year":"1991","unstructured":"D. Eppstein,Offline algorithms for dynamic minimum spanning tree problems, 2nd Worksh. Algorithms and Data Structures, Springer Verlag LNCS 519, 1991, 392\u2013399.","journal-title":"2nd Worksh. Algorithms and Data Structures, Springer Verlag LNCS"},{"key":"BF01994879_CR11","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo, and G. F. Italiano,Sparse dynamic programming, 1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990. 513\u2013522."},{"key":"BF01994879_CR12","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung,Maintenance of a minimum spanning forest in a dynamic planar graph, 1st ACM-SIAM Symp. Discrete Algorithms, 1990, 1\u201311."},{"issue":"4","key":"BF01994879_CR13","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson,Data structures for on-line updating of minimum spanning trees, SIAM J. Comput. 14(4), 1985, 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"BF01994879_CR14","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson,Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, 32nd IEEE Conf. Foundations of Computer Science, 1991, to appear.","DOI":"10.1109\/SFCS.1991.185429"},{"key":"BF01994879_CR15","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1137\/0206011","volume":"6","author":"H. N. Gabow","year":"1977","unstructured":"H. N. Gabow,Two algorithms for generating weighted spanning trees in order, SIAM J. Comput. 6, 1977, 139\u2013150.","journal-title":"SIAM J. Comput."},{"key":"BF01994879_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. N. Gabow","year":"1986","unstructured":"H. N. Gabow, Z. Galil, T. H. Spencer, and R. E. Tarjan,Efficient algorithms for minimum spanning trees on directed and undirected graphs, Combinatorica 6, 1986, 109\u2013122.","journal-title":"Combinatorica"},{"key":"BF01994879_CR17","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/BFb0015746","volume":"194","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and M. Stallman,Efficient algorithms for graphic matroid intersection and parity, 12th Int. Conf. Automata, Languages, and Programming, Springer-Verlag LNCS 194, 1985, 210\u2013220.","journal-title":"12th Int. Conf. Automata, Languages, and Programming, Springer-Verlag LNCS"},{"key":"BF01994879_CR18","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/0210017","volume":"10","author":"N. Katoh","year":"1981","unstructured":"N. Katoh, T. Ibaraki, and H. Mine,An algorithm for finding k minimum spanning trees, SIAM J. Comput. 10, 1981, 247\u2013255.","journal-title":"SIAM J. Comput."},{"key":"BF01994879_CR19","doi-asserted-by":"crossref","unstructured":"E. W. Mayr and C. G. Plaxton,On the spanning trees of weighted graphs, manuscript, 1990.","DOI":"10.1007\/3-540-50728-0_58"},{"issue":"7","key":"BF01994879_CR20","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan,Planar point location using persistent search trees, C. ACM 29(7), 1986, 669\u2013679.","journal-title":"C. ACM"},{"key":"BF01994879_CR21","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. ACM 26, 1979, 690\u2013715.","journal-title":"J. ACM"},{"key":"BF01994879_CR22","first-page":"80","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas,Preserving order in a forest in less than logarithmic time, 16th IEEE Symp. Found. Comput. Sci., 1975, and Info. Proc. Lett. 6, 1977, 80\u201382.","journal-title":"16th IEEE Symp. Found. Comput. Sci."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994879.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01994879\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01994879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T17:37:25Z","timestamp":1586367445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01994879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01994879"],"URL":"https:\/\/doi.org\/10.1007\/bf01994879","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}