{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T05:46:52Z","timestamp":1744264012075,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_73","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:01Z","timestamp":1330275541000},"page":"193-204","source":"Crossref","is-referenced-by-count":15,"title":["On-line and dynamic algorithms for shortest path problems"],"prefix":"10.1007","author":[{"given":"Hristo N.","family":"Djidjev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grammati E.","family":"Pantziou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos D.","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"17_CR1","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.M. Spaccamela, U. Nanni, \u201cIncremental algorithms for minimal length paths\u201d, J. of Algorithms, 12 (1991), pp. 615\u2013638.","journal-title":"J. of Algorithms"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"H. Bondlaender, \u201cDynamic Algorithms for Graphs with Treewidth 2\u201d, Proc. 19th WG'93, LNCS 790, pp. 112\u2013124, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-57899-4_45"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"M. Carroll and B. Ryder, \u201cIncremental Data Flow Analysis via Dominator and Attribute Grammars\u201d, Proc. 15th Ann. ACM POPL, 1988.","DOI":"10.1145\/73560.73584"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"E. Cohen, \u201cEfficient Parallel Shortest-paths in Digraphs with a Separator Decomposition\u201d, Proc. 5th ACM SPAA, 1993, pp. 57\u201367.","DOI":"10.1145\/165231.165240"},{"key":"17_CR5","first-page":"369","volume":"11","author":"H. Djidjev","year":"1985","unstructured":"H. Djidjev, \u201cA Linear Algorithm for Partitioning Graphs of Fixed Genus\u201d, SERDICA, Vol. 11, 1985, pp. 369\u2013387.","journal-title":"SERDICA"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"H. Djidjev, G. Pantziou and C. Zaroliagis, \u201cComputing Shortest Paths and Distances in Planar Graphs\u201d, Proc. 18th ICALP'91, LNCS 510, pp. 327\u2013339, Springer-Verlag.","DOI":"10.1007\/3-540-54233-7_145"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"H. Djidjev, G. Pantziou and C. Zaroliagis, \u201cOn-line and Dynamic Algorithms for Shortest Path Problems\u201d, Tech. Rep. MPI-I-94-114, Max-Planck-Institut f\u00fcr Informatik, April 1994.","DOI":"10.1007\/3-540-59042-0_73"},{"key":"17_CR8","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"S. Even and H. Gazit, \u201cUpdating distances in dynamic graphs\u201d, Methods of Operations Research, Vol. 49, 1985, pp. 371\u2013387.","journal-title":"Methods of Operations Research"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, G. Italiano and A. Nissenzweig, \u201cSparsification \u2014 A Technique for Speeding Up Dynamic Graph Algorithms\u201d, Proc. 33rd FOCS, 1992, pp. 60\u201369.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0304-3975(93)90328-Q","volume":"116","author":"E. Feuerstein","year":"1993","unstructured":"E. Feuerstein and A.M. Spaccamela, \u201cDynamic Algorithms for Shortest Paths in Planar Graphs\u201d, Theor. Computer Science, 116 (1993), pp. 359\u2013371.","journal-title":"Theor. Computer Science"},{"key":"17_CR11","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"G.N. Frederickson, \u201cFast algorithms for shortest paths in planar graphs, with applications\u201d, SIAM J. on Computing, 16 (1987), pp. 1004\u20131022.","journal-title":"SIAM J. on Computing"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cUsing Cellular Graph Embeddings in Solving All Pairs Shortest Path Problems\u201d, Proc. 30th IEEE Symp. on FOCS, 1989, pp. 448\u2013453.","DOI":"10.1109\/SFCS.1989.63517"},{"issue":"No.1","key":"17_CR13","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1145\/102782.102788","volume":"38","author":"G.N. Frederickson","year":"1991","unstructured":"G.N. Frederickson \u201cPlanar Graph Decomposition and All Pairs Shortest Paths\u201d, J. ACM, Vol. 38, No.1, January 1991, pp. 162\u2013204.","journal-title":"J. ACM"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \u201cSearching among Intervals and Compact Routing Tables\u201d, Proc. 20th ICALP'93, LNCS 700, pp. 28\u201339, Springer-Verlag.","DOI":"10.1007\/3-540-56939-1_59"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","volume":"3","author":"G.N. Frederickson","year":"1988","unstructured":"G.N. Frederickson and R. Janardan, \u201cDesigning Networks with Compact Routing Tables\u201d, Algorithmica, 3 (1988), pp. 171\u2013190.","journal-title":"Algorithmica"},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"M. Fredman and R. Tarjan, \u201cFibonacci heaps and their uses in improved network optimization algorithms\u201d, JACM, 34 (1987), pp. 596\u2013615.","journal-title":"JACM"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Z. Galil and G. Italiano, \u201cFully Dynamic Algorithms for Edge-connectivity Problems\u201d, Proc. 23rd ACM STOC, 1991, pp. 317\u2013327.","DOI":"10.1145\/103418.103454"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"H. Gazit and G. Miller, \u201cA Parallel Algorithm for finding a Separator in Planar Graphs\u201d, Proc. 28th IEEE Symp. on FOCS, 1987, pp. 238\u2013248.","DOI":"10.1109\/SFCS.1987.3"},{"key":"17_CR19","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, \u201cMaximum flow in (s, t)-planar networks\u201d, IPL, 13 (1981), p. 107.","journal-title":"IPL"},{"key":"17_CR20","unstructured":"J. J\u00e1J\u00e1, \u201cAn Introduction to Parallel Algorithms\u201d, Addison-Wesley, 1992."},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"D. Kavvadias, G. Pantziou, P. Spirakis and C. Zaroliagis, \u201cHammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems\u201d, Proc. 19th MFCS'94, LNCS 841, pp. 462\u2013472, Springer-Verlag.","DOI":"10.1007\/3-540-58338-6_93"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"D. Kavvadias, G. Pantziou, P. Spirakis and C. Zaroliagis, \u201cEfficient Sequential and Parallel Algorithms for the Negative Cycle Problem\u201d, Proc. 5th ISAAC'94, LNCS 834, pp. 270\u2013278, Springer-Verlag.","DOI":"10.1007\/3-540-58325-4_190"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, M. Rauch and S. Subramanian, \u201cFaster shortest-path algorithms for planar graphs\u201d, Proc. 26th ACM STOC, 1994, pp. 27\u201337.","DOI":"10.1145\/195058.195092"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"J.A. La Poutr\u00e9, \u201cAlpha-Algorithms for Incremental Planarity Testing\u201d, Proc. 26th ACM STOC, 1994, pp. 706\u2013715.","DOI":"10.1145\/195058.195439"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"A. Lingas, \u201cEfficient Parallel Algorithms for Path Problems in Planar Directed Graphs\u201d, Proc. SIGAL'90, LNCS 450, pp. 447\u2013457, 1990, Springer-Verlag.","DOI":"10.1007\/3-540-52921-7_94"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"G. Miller and J. Naor, \u201cFlows in planar graphs with multiple sources and sinks\u201d, Proc. 30th IEEE Symp. on FOCS, 1991, pp. 112\u2013117.","DOI":"10.1109\/SFCS.1989.63464"},{"key":"17_CR27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01994878","volume":"32","author":"G. Pantziou","year":"1992","unstructured":"G. Pantziou, P. Spirakis and C. Zaroliagis, \u201cEfficient Parallel Algorithms for Shortest Paths in Planar Digraphs\u201d, BIT 32 (1992), pp. 215\u2013236.","journal-title":"BIT"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"M. Rauch, \u201cFully Dynamic Biconnectivity in Graphs\u201d, Proc. 33rd IEEE Symp. on FOCS, 1992, pp. 50\u201359.","DOI":"10.1109\/SFCS.1992.267819"},{"key":"17_CR29","unstructured":"G. Ramalingan and T. Reps, \u201cOn the Computational Complexity of Incremental Algorithms\u201d, Technical Report, University of Wisconsin-Madison, 1991."},{"key":"17_CR30","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. Sleator","year":"1983","unstructured":"D. Sleator and R. Tarjan, \u201cA Data Structure for Dynamic Trees\u201d, Journal Comput. System Sci. 26 (1983), pp. 362\u2013391.","journal-title":"Journal Comput. System Sci."},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, \u201cGraph Theoretic Methods in Database Theory\u201d, Proc. ACM conference on Principles of Database Systems, 1990.","DOI":"10.1145\/298514.298576"},{"issue":"2","key":"17_CR32","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/103135.103137","volume":"13","author":"D. Yellin","year":"1991","unstructured":"D. Yellin and R. Strom, \u201cINC: A language for incremental computations\u201d, ACM Trans. Prog. Lang. Systems, 13 (2), pp. 211\u2013236, April 1991.","journal-title":"ACM Trans. Prog. Lang. Systems"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:41:51Z","timestamp":1742596911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}