{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:25:43Z","timestamp":1763641543679},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_18","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:42Z","timestamp":1330249662000},"page":"187-197","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic algorithms for shortest paths in planar graphs"],"prefix":"10.1007","author":[{"given":"Esteban","family":"Feuerstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, U. Nanni, Incremental algorithms for for minimal length paths, Proc. 1 ACM-SIAM Symp. on Discrete Algorithms, S.Francisco, 1990.","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"M. D. Carroll and B. C. Ryder, Incremental data flow analysis via dominator and attribute grammars, Proc. 15th Annual ACM SIGACT-SIGPLAN Symp. on Principles of Programming Languages, 1988.","DOI":"10.1145\/73560.73584"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"G. Di Battista and R.Tamassia, Incremental planarity testing, Proc. 30th annual Symp. on Foundations of Computer Science, 1989.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"G. Di Battista and R.Tamassia, On-line graph algorithms with SPQR-trees, Proc. 17th Int. Coll. on Automata, Languages and Programming, Lect. Not. in Comp. Sci., Springer-Verlag, 1990","DOI":"10.1007\/BFb0032061"},{"key":"18_CR5","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 (1959), pp. 269\u2013271","journal-title":"Numer. Math."},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"H.N. Djidjev, G.E. Pantziou, C.D. Zaroliagis, Computing Shortest Paths and Distances in Planar Graphs, Proc. ICALP 1991, Madrid, to appear in Lect. Not. in Comp. Sci. Springer-Verlag.","DOI":"10.1007\/3-540-54233-7_145"},{"key":"18_CR7","unstructured":"D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, M. Young, Maintenance of a minimum spanning forest in a dynamic planar graph, Proc. 1 ACM-SIAM Symp. on Discrete Algorithms, S.Francisco, 1990."},{"key":"18_CR8","unstructured":"S. Even and H. Gazit, Updating distances in dynamic graphs, Methods of Operations Research 49, 1985."},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci Heaps and their uses in improved Network optimization algorithms, Proc. 25th. IEEE Symp. on Foundations of Computer Science, Singer Island, Oct. 1984, pp. 338\u2013346","DOI":"10.1109\/SFCS.1984.715934"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G. N. Frederickson","year":"1987","unstructured":"G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal Computing, 16 (1987), pp. 1004\u20131022","journal-title":"SIAM Journal Computing"},{"key":"18_CR11","unstructured":"G. N. Frederickson, A new approach to all pairs shortes path in planar graphs, Proc. 19th ACM STOC, New York City, (1987), pp. 19\u201328."},{"key":"18_CR12","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969"},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R. Hassin","year":"1981","unstructured":"R. Hassin, Maximum flow in (s,t) planar networks, Inform. Process. Letters, 13 (1981), p. 107.","journal-title":"Inform. Process. Letters"},{"key":"18_CR14","doi-asserted-by":"publisher","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 J. Appl. Math., 36 (1979), pp. 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"18_CR15","unstructured":"C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Algorithms and Complexity, Prentice Hall, 1982."},{"key":"18_CR16","unstructured":"H. Rohnert, A dynamization of the all-pairs least cost path problem, Proc. of the 2nd Symp. on Theoretical aspects of Computer Science, Lect. Not. in Comp. Sci., vol. 182, Springer-Verlag, 1990."},{"key":"18_CR17","unstructured":"J. Westbrook, Algorithms and data structures for dynamic graph problems, Ph.D. Dissertation, Tech. Rep. CS-TR-229-89, Dept. of Computer Science, Princeton University, 1989."},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Graph Theoretic methods in database theory, Proc. ACM Conf. on Principles of database Systems, 1990.","DOI":"10.1145\/298514.298576"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"D. M. Yellin and R. Strom, INC: a language for incremental computations, Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation, 1988.","DOI":"10.1145\/53990.54002"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T04:12:38Z","timestamp":1640923958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}