{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T09:30:06Z","timestamp":1743327006542},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-58715-2_118","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:40:54Z","timestamp":1330256454000},"page":"113-124","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Incremental algorithms for the single-source shortest path problem"],"prefix":"10.1007","author":[{"given":"Daniele","family":"Frigioni","sequence":"first","affiliation":[]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[]},{"given":"Umberto","family":"Nanni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"10_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient Algorithms for Combinatorial Problems on Graphs with Bounded Decomposability \u2014 A survey, BIT, 25, 2\u201323, 1985.","journal-title":"BIT"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, T. Kloks, Approximating Treewidth, Path-width, and Minimum Elimination Tree Height, Proceedings International Workshop on Graph-theoretic Concepts in Computer Science (WG 91), Lecture Notes in Computer Science, 570, Springer-Verlag, 1\u201313.","DOI":"10.1007\/3-540-55121-2_1"},{"issue":"4","key":"10_CR4","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/0196-6774(91)90036-X","volume":"12","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, and U. Nanni, Incremental Algorithms for Minimal Length Paths, Journal of Algorithms, 12, 4 (December 1991), 615\u2013638.","journal-title":"Journal of Algorithms"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"E. W. Dijkstra, A note on two problems in connection with graphs, Numerical Mathematics 1, 1959.","DOI":"10.1007\/BF01386390"},{"key":"10_CR6","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"S. Even, and H. Gazit, Updating distances in dynamic graphs, Methods of Operations Research 49 (1985), 371\u2013387.","journal-title":"Methods of Operations Research"},{"key":"10_CR7","unstructured":"E. Feuerstein, and A. Marchetti-Spaccamela, On-line Algorithms for Shortest Paths in Planar Graphs, Theoretical Computer Science, to appear."},{"key":"10_CR8","first-page":"6","volume":"16","author":"G. N. Frederickson","year":"1987","unstructured":"G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, 16, 6, (December 1987).","journal-title":"SIAM Journal on Computing"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"F. Harary, Graph Theory, Addison-Wesley (1969).","DOI":"10.21236\/AD0705364"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"P, N. Klein, S. Rao, M. Rauch and S. Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings ACM Symposium on Theory of Computing (1994), to appear.","DOI":"10.1145\/195058.195092"},{"key":"10_CR11","unstructured":"P. N. Klein and S. Subramanian, Fully Dynamic Approximation Schemes for Shortest Path Problems in Planar Graphs, Proceedings International Workshop on Algorithms and Data Structures (WADS 93)."},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, A Separator Theorem for Planar Graphs, SIAM Journal of Applied Mathematics, 36 (1979), 177\u2013189.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"10_CR13","series-title":"Tech. Rep.","volume-title":"On the computational complexity of Incremental Algorithms","author":"G. Ramalingam","year":"1991","unstructured":"G. Ramalingam and T. Reps, On the computational complexity of Incremental Algorithms, Tech. Rep. Computer Science Department, University of Wisconsin, Madison (1991)."},{"key":"10_CR14","series-title":"Tech. Rep.","volume-title":"An Incremental Algorithm for a Generalization of the Shortest Path Problem","author":"G. Ramalingam","year":"1992","unstructured":"G. Ramalingam and T. Reps, An Incremental Algorithm for a Generalization of the Shortest Path Problem, Tech. Rep. n. 1087, Computer Science Department, University of Wisconsin, Madison (1992)."},{"key":"10_CR15","series-title":"Tech. Rep.","volume-title":"Bounded Incremental Computation","author":"G. Ramalingam","year":"1993","unstructured":"G. Ramalingam, Bounded Incremental Computation, Tech. Rep. 1172, Computer Science Department, University of Wisconsin, Madison (August 1993)."},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"H. Rohnert, A dynamization of the all-pairs least cost path problem, Proceedings 2nd Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 182, Springer-Verlag (1990), 279\u2013286.","DOI":"10.1007\/BFb0024016"},{"key":"10_CR17","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 Journal on Algebraic and Discrete Methods, 6 (1985), 306\u2013318.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:50:57Z","timestamp":1578509457000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_118"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_118","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}