{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:17:13Z","timestamp":1781259433936,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540676904","type":"print"},{"value":"9783540449850","type":"electronic"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_1","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T20:17:33Z","timestamp":1194985053000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Dynamic Graph Algorithms with Applications"],"prefix":"10.1007","author":[{"given":"Mikkel","family":"Thorup","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Karger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"1_CR1","series-title":"Discrete Mathematics and Optimization","volume-title":"Local Search in Combinatorial Optimization","year":"1997","unstructured":"E. H. L. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. Discrete Mathematics and Optimization. Wiley-Interscience, Chichester, England, June 1997."},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho","year":"1981","unstructured":"A.V. Aho, Y. Sagiv, T.G. Szymanski, and J.D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Computing, 10(3):405\u2013421, 1981.","journal-title":"SIAM J. Computing"},{"key":"1_CR3","unstructured":"T.C. Biedl, P. Bose, E.D. Demaine, and A. Lubiw. Efficient algorithms for Petersen\u2019s matching theorem. In Proc. 10th ACM-SIAM Symp. on Discrete Algorithms,pages 130\u2013139, 1999."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connection with graphs. Numer. Math., 1:269\u2013271, 1959.","journal-title":"Numer. Math"},{"issue":"5","key":"1_CR5","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification \u2014 a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669\u2013696, 1997. See also FOCS\u201992.","journal-title":"J. ACM"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proc. 19th IEEE INFOCOM-Conf. Computer Communications, pages 519\u2013528, 2000.","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/297096.297147","volume":"3","author":"D. Frigioni","year":"1998","unstructured":"D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasqualone. Experimental analysis of dynamic algorithms for the single-source shortest path problem. ACM J. Experimental Algorithmics, 3, article 5, 1998.","journal-title":"ACM J. Experimental Algorithmics"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"H. N. Gabow","year":"1995","unstructured":"H. N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comp. Syst. Sc., 50:259\u2013273, 1995.","journal-title":"J. Comp. Syst. Sc."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"H.N. Gabow, H. Kaplan, and R.E. Tarjan. Unique maximum matching algorithms. In Proc. 31st ACM Symp. on Theory of Computing, pages 70\u201378, 1999.","DOI":"10.1145\/301250.301273"},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009268","volume":"24","author":"M.R. Henzinger","year":"1999","unstructured":"M.R. Henzinger, V. King, and T. Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica, 24(1):1\u201313, 1999.","journal-title":"Algorithmica"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In Proc. 30th ACM Symp. on Theory of Computing, pages 79\u201389, 1998.","DOI":"10.1145\/276698.276715"},{"issue":"6","key":"1_CR12","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1137\/S0097539795287642","volume":"27","author":"S. Kannan","year":"1998","unstructured":"S. Kannan, T. Warnow, and S. Yooseph. Computing the local consensus of trees. SIAM J. Computing, 27(6):1695\u20131724, 1998.","journal-title":"SIAM J. Computing"},{"key":"1_CR13","unstructured":"D. R. Karger. Using randomized sparsification to approximate minimum cuts. In Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, pages 424\u2013432, 1994."},{"key":"1_CR14","unstructured":"D. R. Karger. Better random sampling algorithms for flows in undirected graphs. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, pages 490\u2013499, 1998."},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"D. R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1), 2000.","DOI":"10.1145\/331605.331608"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. 40th IEEE Symp. on Foundations of Computer Science, pages 81\u201389, 1999.","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"1_CR17","first-page":"73","volume":"9","author":"A. Kotzig","year":"1959","unstructured":"A. Kotzig. On the theory of finite graphs with a linear factor I. Mat.-Fyz. Casopis Slovensk. Akad. Vied, 9:73\u201391, 1959.","journal-title":"Mat.-Fyz. Casopis Slovensk. Akad. Vied"},{"key":"1_CR18","unstructured":"D. W. Matula. A linear time 2 + \u2208 approximation algorithm for edge connectivity. In Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pages 500\u2013504, 1993."},{"key":"1_CR19","unstructured":"J. T. Moy. OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley, 1999."},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki. Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583\u2013596, 1992.","journal-title":"Algorithmica"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"C. St. J. A. Nash-Williams","year":"1991","unstructured":"C. St. J. A. Nash-Williams. Edge disjoint spanning trees of finite graphs. J. London Math. Soc., 36:445\u2013450, 1991.","journal-title":"J. London Math. Soc"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"J. Petersen. Die theorie der regul\u00e4ren graphs. Acta Mathematica, 15:193\u2013220, 1891.","journal-title":"Acta Mathematica"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S. A. Plotkin","year":"1995","unstructured":"S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20:257\u2013301, 1995.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"1_CR24","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267\u2013305, 1996.","journal-title":"J. Algorithms"},{"key":"1_CR25","unstructured":"N. Young. Randomized rounding without solving the linear program. In Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 170\u2013178, 1995."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T08:18:30Z","timestamp":1737533910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"15 March 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}