{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:08:38Z","timestamp":1763467718136},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_96","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"964-973","source":"Crossref","is-referenced-by-count":24,"title":["Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"96_CR1","unstructured":"Alon, A., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical Report TR-71\/87, Institute of Computer Science, Tel Aviv University (1987)"},{"key":"96_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"96_CR3","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for LCAs, MST verification, and dominators. In: Proc.\u00a030th ACM Symposium on Theory of Computing (STOC), pp. 279\u2013288 (1998)","DOI":"10.1145\/276698.276764"},{"issue":"3","key":"96_CR4","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica\u00a02(3), 337\u2013361 (1987)","journal-title":"Algorithmica"},{"issue":"6","key":"96_CR5","first-page":"1028","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J.\u00a0ACM\u00a047(6), 1028\u20131047 (2000)","journal-title":"J.\u00a0ACM"},{"issue":"6","key":"96_CR6","first-page":"1012","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: The soft heap: an approximate priority queue with optimal error rate. J.\u00a0ACM\u00a047(6), 1012\u20131027 (2000)","journal-title":"J.\u00a0ACM"},{"issue":"6","key":"96_CR7","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J.\u00a0Comput.\u00a021(6), 1184\u20131192 (1992)","journal-title":"SIAM J.\u00a0Comput."},{"key":"96_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Saks, M.: The cell probe complexity of dynamic data structures. In: Proc. 21st ACM Symposium on Theory of Computing, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"key":"96_CR9","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: Proc.\u00a026th Symp.\u00a0on Foundations of Computer Science (FOCS), pp. 90\u2013100 (1985)","DOI":"10.1109\/SFCS.1985.3"},{"key":"96_CR10","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"96_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a030(2), 209\u2013221 (1985)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"4","key":"96_CR12","first-page":"815","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph-matching problems. J.\u00a0ACM\u00a038(4), 815\u2013853 (1991)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"96_CR13","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/0222020","volume":"22","author":"W. Goddard","year":"1993","unstructured":"Goddard, W., Kenyon, C., King, V., Schulman, L.: Optimal randomized algorithms for local sorting and set-maxima. SIAM J.\u00a0Comput.\u00a022(2), 272\u2013283 (1993)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1","key":"96_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput.\u00a07(1), 43\u201357 (1985)","journal-title":"Ann. Hist. Comput."},{"key":"96_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-45022-X_7","volume-title":"Automata, Languages and Programming","author":"T. Hagerup","year":"2000","unstructured":"Hagerup, T.: Improved shortest paths on the word RAM. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 61\u201372. Springer, Heidelberg (2000)"},{"key":"96_CR16","first-page":"321","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J.\u00a0ACM\u00a042, 321\u2013329 (1995)","journal-title":"J.\u00a0ACM"},{"key":"96_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/978-3-540-39658-1_61","volume-title":"Algorithms - ESA 2003","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Sanders, P., Tr\u00e4ff, J.L.: A practical minimum spanning tree algorithm using the cycle property. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 679\u2013690. Springer, Heidelberg (2003)"},{"issue":"2","key":"96_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V. King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica\u00a018(2), 263\u2013270 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"96_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02579443","volume":"5","author":"J. Koml\u00f3s","year":"1985","unstructured":"Koml\u00f3s, J.: Linear verification for spanning trees. Combinatorica\u00a05(1), 57\u201365 (1985)","journal-title":"Combinatorica"},{"key":"96_CR20","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jcss.1996.0008","volume":"52","author":"H. LaPoutr\u00e9","year":"1996","unstructured":"LaPoutr\u00e9, H.: Lower bounds for the union-find and the split-find problem on pointer machines. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a052, 87\u201399 (1996)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"96_CR21","doi-asserted-by":"crossref","unstructured":"Pettie, S.: An inverse-Ackermann type lower bound for online minimum spanning tree verification. Combinatorica (to appear)","DOI":"10.1007\/s00493-006-0014-1"},{"key":"96_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-36136-7_4","volume-title":"Algorithms and Computation","author":"S. Pettie","year":"2002","unstructured":"Pettie, S.: On the comparison-addition complexity of all-pairs shortest paths. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 32\u201343. Springer, Heidelberg (2002)"},{"key":"96_CR23","unstructured":"Pettie, S.: On the Shortest Path and Minimum Spanning Tree Problems. Ph.D. thesis, The University of Texas at Austin, Department of Computer Sciences Technical Report TR-03-35 (2003)"},{"issue":"1","key":"96_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S. Pettie","year":"2004","unstructured":"Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science\u00a0312(1), 47\u201374 (2004)","journal-title":"Theoretical Computer Science"},{"key":"96_CR25","unstructured":"Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In: Proc.\u00a013th Ann.\u00a0ACM-SIAM Symp.\u00a0on Discrete Algorithms (SODA), pp. 713\u2013722 (2002)"},{"issue":"1","key":"96_CR26","first-page":"16","volume":"49","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J.\u00a0ACM\u00a049(1), 16\u201334 (2002)","journal-title":"J.\u00a0ACM"},{"key":"96_CR27","unstructured":"Pettie, S., Ramachandran, V.: New randomized minimum spanning tree algorithms using exponentially fewer random bits (manuscript) (submitted, 2005)"},{"issue":"6","key":"96_CR28","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J.\u00a0Comput.\u00a034(6), 1398\u20131431 (2005)","journal-title":"SIAM J.\u00a0Comput."},{"key":"96_CR29","first-page":"215","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set merging algorithm. J.\u00a0ACM\u00a022, 215\u2013225 (1975)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"96_CR30","first-page":"690","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J.\u00a0ACM\u00a026(4), 690\u2013715 (1979)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"96_CR31","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a018(2), 110\u2013127 (1979)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"1","key":"96_CR32","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R.E. Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path problems. Info.\u00a0Proc.\u00a0Lett.\u00a014(1), 30\u201333 (1982), See Corrigendum, IPL\u00a023(4), 219","journal-title":"Info.\u00a0Proc.\u00a0Lett."},{"issue":"3","key":"96_CR33","first-page":"362","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J.\u00a0ACM\u00a046(3), 362\u2013394 (1999)","journal-title":"J.\u00a0ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_96.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:03:17Z","timestamp":1619506997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11602613_96","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}